
\chapter{Applicative functors and contrafunctors\label{chap:8-Applicative-functors,-contrafunc}}

\section{Slides, Part I}

\paragraph{Motivation for applicative functors}

\vspace{-0.25cm}Monads are inconvenient for expressing \emph{independent}
effects

Monads perform effects \emph{sequentially} even if effects are independent:\texttt{\textcolor{blue}{\footnotesize{}\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~Future~\{~c1~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}y~$\leftarrow$~Future~\{~c2~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~Future~\{~c3~\}}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}Future~\{~c1~\}.flatMap~\{~x~$\rightarrow$}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~Future~\{~c2~\}.flatMap~\{~y~$\rightarrow$}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~Future~\{~c3~\}.map~\{~z~$\rightarrow$~...\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~\}}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

We would like to parallelize independent computations

We would like to accumulate \emph{all} errors, rather than stop at
the first one

Changing the order of monad\textsf{'}s effects will (generally) change the
result:\texttt{\textcolor{blue}{\footnotesize{}\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~List(1,~2)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~List(10,~20)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x,~y)}{\footnotesize\par}

\textrm{\textcolor{gray}{\footnotesize{}//~f(1,~10),~f(1,~20),~f(2,~10),~f(2,~20)}}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~List(10,~20)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~List(1,~2)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x,~y)}{\footnotesize\par}

\textrm{\textcolor{gray}{\footnotesize{}//~f(1,~10),~f(2,~10),~f(1,~20),~f(2,~20)}}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

We would like to express a computation where effects are unordered

This can be done using a method \texttt{\textcolor{blue}{\footnotesize{}map2}},
\emph{not} defined via \texttt{\textcolor{blue}{\footnotesize{}flatMap}}:
the desired type signature is {\footnotesize{}$\text{map2}:F^{A}\times F^{B}\rightarrow\left(A\times B\rightarrow C\right)\rightarrow F^{C}$} 

\textbf{Applicative functor} has \texttt{\textcolor{blue}{\footnotesize{}map2}}
and \texttt{\textcolor{blue}{\footnotesize{}pure}} but is not necessarily
a monad


\paragraph{Defining \texttt{\textcolor{blue}{\footnotesize{}map2}}, \texttt{\textcolor{blue}{\footnotesize{}map3}},
etc.}

\vspace{-0.15cm}Consider 1, 2, 3, ... commutative and independent
\textsf{``}effects\textsf{''}

\texttt{\textcolor{blue}{\footnotesize{}\hrule\medskip{}
}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x1~$\leftarrow$~c1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x1)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}c1.map(f)}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}\hrule\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x1~$\leftarrow$~c1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x2~$\leftarrow$~c2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x1,~x2)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}(c1,~c2).map2(f)}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
\hrule\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x~$\leftarrow$~c1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x2~$\leftarrow$~c2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x3~$\leftarrow$~c3}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x1,~x2,~x3)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}(c1,~c2,~c3).map3(f)}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
\hrule\medskip{}
}}{\footnotesize\par}

Generalize from \texttt{\textcolor{blue}{\footnotesize{}map}}, \texttt{\textcolor{blue}{\footnotesize{}map2}},
\texttt{\textcolor{blue}{\footnotesize{}map3}} to \texttt{\textcolor{blue}{\footnotesize{}mapN}}:
\begin{align*}
\text{map}_{1} & :F^{A}\rightarrow\left(A\rightarrow Z\right)\rightarrow F^{Z}\\
\text{map}_{2} & :F^{A}\times F^{B}\rightarrow\left(A\times B\rightarrow Z\right)\rightarrow F^{Z}\\
\text{map}_{3} & :F^{A}\times F^{B}\times F^{C}\rightarrow\left(A\times B\times C\rightarrow Z\right)\rightarrow F^{Z}
\end{align*}


\paragraph{Practical examples of using \texttt{\textcolor{blue}{\footnotesize{}mapN}} }

\vspace{-0.2cm}$F^{A}\triangleq Z+A$ where $Z$ is a monoid: collect
all errors

$F^{A}=Z+A$: Create a validated case class out of validated parts

$F^{A}\triangleq$ \texttt{\textcolor{blue}{\footnotesize{}Future{[}A{]}}}:
perform several computations concurrently

$F^{A}\triangleq E\rightarrow A$: pass standard arguments to functions
more easily

$F^{A}\triangleq\text{List}^{A}$: transposing a matrix by using \texttt{\textcolor{blue}{\footnotesize{}map2}} 

Applicative contrafunctors and applicative profunctors

defining an instance of \texttt{\textcolor{blue}{\footnotesize{}Semigroup}}
type class from \texttt{\textcolor{blue}{\footnotesize{}Semigroup}}
parts

implement \texttt{\textcolor{blue}{\footnotesize{}imap2}} for non-disjunctive
profunctors, e.g.\ $Z\times A\rightarrow A\times A$

\textsf{``}Fused \texttt{\textcolor{blue}{\footnotesize{}fold}}\textsf{''}: automatically
merge several \texttt{\textcolor{blue}{\footnotesize{}fold}}s into
one

compute several running averages in one traversal (\href{https://github.com/amarpotghan/scala-fold}{scala-folds})

The difference between applicative and monadic functors

define monadic folds using the \textsf{``}free functor\textsf{''} construction

compute running averages that depend on previous running averages

do not confuse this with \emph{monad-valued} folds (\href{https://github.com/atnos-org/origami}{origami})!

applicative parsers vs.\ monadic parsers

applicative: parse independent data, collecting all errors

monadic: parse depends on previous results, stops on errors

monads, applicatives, arrows paper: (Lindley, Wadler, Yallop) 

mumbo-jumbo, clap-trap, abra-cadabra, algebra-cadalgebra, gobbledy-gook


\subsection{Exercises I }

Implement \texttt{\textcolor{blue}{\footnotesize{}map2}}, or \texttt{\textcolor{blue}{\footnotesize{}imap2}}
if appropriate, for these type constructors $F^{A}$:

$F^{A}\triangleq1+A+A\times A$

$F^{A}\triangleq E\rightarrow A\times A$

$F^{A}\triangleq Z\times A\rightarrow A$ 

$F^{A}\triangleq A\rightarrow A\times Z$ where $Z$ is a \texttt{\textcolor{blue}{\footnotesize{}Monoid}} 

Write a function that defines an instance of the \texttt{\textcolor{blue}{\footnotesize{}Monoid}}
type class for a tuple $\left(A,B\right)$ whose parts already have
a \texttt{\textcolor{blue}{\footnotesize{}Monoid}} instance.

Define a \texttt{\textcolor{blue}{\footnotesize{}Monoid}} instance
for the type $F^{S}$ where $F$ is an applicative functor that has
\texttt{\textcolor{blue}{\footnotesize{}map2}} and \texttt{\textcolor{blue}{\footnotesize{}pure}},
while $S$ is itself a monoid type.

Define a \textsf{``}regexp extractor\textsf{''} as a type constructor $R^{A}$ describing
extraction of various data from strings; the extracted data is converted
to a value of type \texttt{\textcolor{blue}{\footnotesize{}Option{[}A{]}}}.
Implement \texttt{\textcolor{blue}{\footnotesize{}zip}} and \texttt{\textcolor{blue}{\footnotesize{}map2}}
for $R^{A}$.

Use parser combinators to implement an evaluator for arithmetic language
containing only decimal digits and $+$ symbols, for example $1+321+20$.

Use folding combinators to implement a \texttt{\textcolor{blue}{\footnotesize{}Fold}}
that computes the standard deviation of a sequence in one traversal.

\section{Slides, Part II}

\paragraph{Deriving the \texttt{\textcolor{blue}{\footnotesize{}ap}} operation
from \texttt{\textcolor{blue}{\footnotesize{}map2}} }

\vspace{-0.1cm}Can we avoid having to define $\text{map}_{n}$ separately
for each $n$?
\begin{itemize}
\item Use curried arguments, $\text{fmap}_{2}:(A\rightarrow B\rightarrow Z)\rightarrow F^{A}\rightarrow F^{B}\rightarrow F^{Z}$
\begin{itemize}
\item Set $A\triangleq\left(B\rightarrow Z\right)$ and apply $\text{fmap}_{2}$
to the identity $\text{id}^{\left(B\rightarrow Z\right)\rightarrow\left(B\rightarrow Z\right)}$:
obtain $\text{ap}^{[B,Z]}:F^{B\rightarrow Z}\rightarrow F^{B}\rightarrow F^{Z}\triangleq\text{fmap}_{2}\left(\text{id}\right)$
\item The functions \texttt{\textcolor{blue}{\footnotesize{}fmap$_{2}$}}
and \texttt{\textcolor{blue}{\footnotesize{}ap}} are computationally
equivalent:{\footnotesize{}
\[
\text{fmap}_{2}\,f^{A\rightarrow B\rightarrow Z}=\text{fmap}\,f\bef\text{ap}
\]
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{B\rightarrow Z}\ar[rd]\sp(0.45){\text{ap}}\\
F^{A}\ar[ru]\sp(0.45){\text{fmap}\,f}\ar[rr]\sb(0.45){\text{fmap}_{2}\,(f^{A\rightarrow B\rightarrow Z})} &  & \left(F^{B}\rightarrow F^{Z}\right)
}
\]
}{\footnotesize\par}
\item The functions \texttt{\textcolor{blue}{\footnotesize{}fmap$_{3}$}},
\texttt{\textcolor{blue}{\footnotesize{}fmap$_{4}$}} etc.\ can be
defined similarly:{\footnotesize{}
\[
\text{fmap}_{3}\,f^{A\rightarrow B\rightarrow C\rightarrow Z}=\text{fmap}\,f\bef\text{ap}\bef\text{fmap}_{F^{B}\rightarrow?}\text{ap}
\]
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{B\rightarrow C\rightarrow Z}\ar[r]\sp(0.45){\text{ap}^{[B,C\rightarrow Z]}} & \left(F^{B}\rightarrow F^{C\rightarrow Z}\right)\ar[rd]\sp(0.55){\text{fmap}_{F^{B}\rightarrow?}\text{ap}^{[C,Z]}}\\
F^{A}\ar[ru]\sp(0.45){\text{fmap}\,f}\ar[rrr]\sb(0.45){\text{fmap}_{3}\,(f^{A\rightarrow B\rightarrow C\rightarrow Z})} &  &  & \left(F^{B}\rightarrow F^{C}\rightarrow F^{Z}\right)
}
\]
}{\footnotesize\par}
\item Using the infix syntax will get rid of {\footnotesize{}$\text{fmap}_{F^{B}\rightarrow?}\text{ap}$}
(see example code)
\begin{itemize}
\item Note the pattern: a natural transformation is equivalent to a lifting
\end{itemize}
\end{itemize}
\end{itemize}


\paragraph{Deriving the \texttt{\textcolor{blue}{\footnotesize{}zip}} operation
from \texttt{\textcolor{blue}{\footnotesize{}map2}} }
\begin{itemize}
\item The types $A\rightarrow B\rightarrow C$ and $A\times B\rightarrow C$
are equivalent (curry/uncurry)
\begin{itemize}
\item Uncurry $\text{fmap}_{2}$ to $\text{fmap2}:\left(A\times B\rightarrow C\right)\rightarrow F^{A}\times F^{B}\rightarrow F^{C}$ 
\item Compute $\text{fmap2}\left(f\right)$ with $f=\text{id}^{A\times B\rightarrow A\times B}$,
expecting to obtain a simpler natural transformation: 
\[
\text{zip}:F^{A}\times F^{B}\rightarrow F^{A\times B}
\]
 
\item This is quite similar to \texttt{\textcolor{blue}{\footnotesize{}zip}}
for lists:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}List(1,~2).zip(List(10,~20))~=~List((1,~10),~(2,~20))}~
\end{lyxcode}
\begin{itemize}
\item The functions \texttt{\textcolor{blue}{\footnotesize{}zip}} and \texttt{\textcolor{blue}{\footnotesize{}fmap2}}
are computationally equivalent:{\footnotesize{}
\begin{align*}
\text{zip} & =\text{fmap2}\left(\text{id}\right)\\
\text{fmap2}\,(f^{A\times B\rightarrow C}) & =\text{zip}\bef\text{fmap}\,f
\end{align*}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{A\times B}\ar[rd]\sp(0.65){\ \ \text{fmap}\,f^{A\times B\rightarrow C}}\\
F^{A}\times F^{B}\ar[ru]\sp(0.5){\text{zip}}\ar[rr]\sb(0.6){\text{fmap2}\,(f^{A\times B\rightarrow C})} &  & F^{C}
}
\]
}{\footnotesize\par}
\item The functor $F$ is \textbf{zippable} if such a \texttt{\textcolor{blue}{\footnotesize{}zip}}
exists (with appropriate laws)
\begin{itemize}
\item The same pattern: a natural transformation is equivalent to a lifting
\end{itemize}
\end{itemize}
\end{itemize}


\paragraph{{*} Equivalence of the operations \texttt{\textcolor{blue}{\footnotesize{}ap}}
and \texttt{\textcolor{blue}{\footnotesize{}zip}} }
\begin{itemize}
\item \vspace{-0.2cm}Set $A\triangleq B\rightarrow C$, get $\text{zip}^{[B\rightarrow C,B]}:F^{B\rightarrow C}\times F^{B}\rightarrow F^{(B\rightarrow C)\times B}$
\begin{itemize}
\item Use \texttt{\textcolor{blue}{\footnotesize{}eval}} $:\left(B\rightarrow C\right)\times B\rightarrow C$
and $\text{fmap}\left(\text{eval}\right):F^{(B\rightarrow C)\times B}\rightarrow F^{C}$
\item Uncurry: \texttt{\textcolor{blue}{\footnotesize{}app}}$\text{}^{[B,C]}:F^{B\rightarrow C}\times F^{B}\rightarrow F^{C}\triangleq\text{zip}\bef\text{fmap}\left(\text{eval}\right)$ 
\item The functions \texttt{\textcolor{blue}{\footnotesize{}zip}} and \texttt{\textcolor{blue}{\footnotesize{}app}}
are computationally equivalent:
\begin{itemize}
\item use $\text{pair}:\left(A\rightarrow B\rightarrow A\times B\right)=a^{A}\rightarrow b^{B}\rightarrow a\times b$
\item use $\text{fmap}\left(\text{pair}\right)\triangleq\text{pair}^{\uparrow}$
on an $fa^{F^{A}}$, get $(\text{pair}^{\uparrow}fa):F^{B\rightarrow A\times B}$;
then{\footnotesize{}
\begin{align*}
\text{zip}\left(fa\times fb\right) & =\text{app}\left((\text{pair}^{\uparrow}fa)\times fb\right)\\
\text{app}^{[B,C]} & =\text{zip}^{[B\rightarrow C,B]}\bef\text{fmap}\left(\text{eval}\right)
\end{align*}
}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{(B\rightarrow C)\times B}\ar[rd]\sp(0.65){\ \ \text{fmap}\left(\text{eval}\right)}\\
F^{B\rightarrow C}\times F^{B}\ar[ru]\sp(0.5){\text{zip}}\ar[rr]\sb(0.55){\text{app}^{[B,C]}} &  & F^{C}
}
\]
\end{itemize}
\item Rewrite this using curried arguments: $\text{fzip}^{[A,B]}:F^{A}\rightarrow F^{B}\rightarrow F^{A\times B}$;
$\text{ap}^{[B,C]}:F^{B\rightarrow C}\rightarrow F^{B}\rightarrow F^{C}$;
then $\text{ap}\,f=\text{fzip}\,f\bef\text{fmap}\left(\text{eval}\right)$. 
\item Now $\text{fzip}\,p^{F^{A}}q^{F^{B}}=\text{ap}\left(\text{pair}^{\uparrow}p\right)q$,
hence we may omit the argument $q$: $\text{fzip}=\text{pair}^{\uparrow}\bef\text{ap}$.
With explicit types: $\text{fzip}^{[A,B]}=\text{pair}^{\uparrow}\bef\text{ap}^{[B,A\rightarrow B]}$.
\end{itemize}
\end{itemize}


\paragraph{Motivation for applicative laws. Naturality laws for \texttt{\textcolor{blue}{\footnotesize{}map2}} }

Treat \texttt{\textcolor{blue}{\footnotesize{}map2}} as a replacement
for a monadic block with independent effects:\texttt{\textcolor{blue}{\footnotesize{}\smallskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(x,~y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}map2~(}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~cont1,}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{})~\{~(x,~y)~$\rightarrow$~g(x,~y)~\}}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}
\begin{itemize}
\item Main idea: Formulate the monad laws in terms of \texttt{\textcolor{blue}{\footnotesize{}map2}}
and \texttt{\textcolor{blue}{\footnotesize{}pure}} 

Naturality laws: Manipulate data in one of the containers\texttt{\textcolor{blue}{\footnotesize{}\smallskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~cont1.map(f)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(x,~y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(f(x),~y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

and similarly for \texttt{\textcolor{blue}{\footnotesize{}cont2}}
instead of \texttt{\textcolor{blue}{\footnotesize{}cont1}}; now rewrite
in terms of for \texttt{\textcolor{blue}{\footnotesize{}map2}}:
\begin{itemize}
\item \textbf{Left naturality} for \texttt{\textcolor{blue}{\footnotesize{}map2}}:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}map2(cont1.map(f),~cont2)(g)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~=~map2(cont1,~cont2)\{~(x,~y)~$\rightarrow$~g(f(x),~y)~\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item \textbf{Right naturality} for \texttt{\textcolor{blue}{\footnotesize{}map2}}:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}map2(cont1,~cont2.map(f))(g)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~=~map2(cont1,~cont2)\{~(x,~y)~$\rightarrow$~g(x,~f(y))~\}}{\footnotesize\par}
\end{lyxcode}
\end{itemize}


\paragraph{Associativity and identity laws for \texttt{\textcolor{blue}{\footnotesize{}map2}} }

\vspace{-0.1cm}Inline two generators out of three, in two different
ways:\texttt{\textcolor{blue}{\footnotesize{}\smallskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~(y,~z)~$\leftarrow$~for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~~~yy~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~~~zz~$\leftarrow$~cont3}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~\}~yield~(yy,~zz)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(x,~y,~z)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~(x,~y)~$\leftarrow$~for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~~~~~~~~xx~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~~~~~~~~yy~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~~~~~~\}~yield~(xx,~yy)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~z~$\leftarrow$~cont3}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(x,~y,~z)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

Write this in terms of \texttt{\textcolor{blue}{\footnotesize{}map2}}
to obtain the \textbf{associativity law} for \texttt{\textcolor{blue}{\footnotesize{}map2}}:
\begin{lyxcode}
\vspace{-0.1cm}\textcolor{blue}{\footnotesize{}map2(cont1,~map2(cont2,~cont3)((\_,\_))\{~case(x,(y,z))$\rightarrow$g(x,y,z)\}}{\footnotesize\par}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}~~=~map2(map2(cont1,~cont2)((\_,\_)),~cont3)\{~case((x,y),z))$\rightarrow$g(x,y,z)\}}~
\end{lyxcode}
Empty context precedes a generator, or follows a generator:\textcolor{blue}{\footnotesize{}\smallskip{}
}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x~$\leftarrow$~pure(a)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~y~$\leftarrow$~cont}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(x,~y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\textcolor{blue}{\footnotesize{}\hfill{}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~cont}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(a,~y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}{\footnotesize\par}

Write this in terms of \textcolor{blue}{\footnotesize{}map2} to obtain
the \textbf{identity laws} for \textcolor{blue}{\footnotesize{}map2}
and \textcolor{blue}{\footnotesize{}pure}:
\begin{lyxcode}
\vspace{-0.1cm}\textcolor{blue}{\footnotesize{}map2(pure(a),~cont)(g)~=~cont.map~\{~y~$\rightarrow$~g(a,~y)~\}}~

\textcolor{blue}{\footnotesize{}map2(cont,~pure(b))(g)~=~cont.map~\{~x~$\rightarrow$~g(x,~b)~\}}~
\end{lyxcode}
\end{lyxcode}


\paragraph{Deriving the laws for \texttt{\textcolor{blue}{\footnotesize{}zip}}:
naturality law}
\begin{itemize}
\item \vspace{-0.2cm}The laws for \texttt{\textcolor{blue}{\footnotesize{}map2}}
in a short notation; here{\footnotesize{} $f\otimes g\triangleq\left\{ a\times b\rightarrow f(a)\times g(b)\right\} $}
{\footnotesize{}
\begin{align*}
\text{fmap2}\left(g^{A\times B\rightarrow C}\right)\left(f^{\uparrow}q_{1}\times q_{2}\right) & =\text{fmap2}\left(\left(f\otimes\text{id}\right)\bef g\right)\left(q_{1}\times q_{2}\right)\\
\text{fmap2}\left(g^{A\times B\rightarrow C}\right)\left(q_{1}\times f^{\uparrow}q_{2}\right) & =\text{fmap2}\left(\left(\text{id}\otimes f\right)\bef g\right)\left(q_{1}\times q_{2}\right)\\
\text{fmap2}\left(g_{1.23}\right)\left(q_{1}\times\text{fmap2}\left(\text{id}\right)\left(q_{2}\times q_{3}\right)\right) & =\text{fmap2}\left(g_{12.3}\right)\left(\text{fmap2}\left(\text{id}\right)\left(q_{1}\times q_{2}\right)\times q_{3}\right)\\
\text{fmap2}\left(g^{A\times B\rightarrow C}\right)\left(\text{pure}\,a^{A}\times q_{2}^{F^{B}}\right) & =\left(b\rightarrow g\left(a\times b\right)\right)^{\uparrow}q_{2}\\
\text{fmap2}\left(g^{A\times B\rightarrow C}\right)\left(q_{1}^{F^{A}}\times\text{pure}\,b^{B}\right) & =\left(a\rightarrow g\left(a\times b\right)\right)^{\uparrow}q_{1}
\end{align*}
}{\footnotesize\par}
\begin{itemize}
\item Express \texttt{\textcolor{blue}{\footnotesize{}map2}} through \texttt{\textcolor{blue}{\footnotesize{}zip}}:{\footnotesize{}
\begin{align*}
\text{fmap}_{2}\,g^{A\times B\rightarrow C}\left(q_{1}^{F^{A}}\times q_{2}^{F^{B}}\right) & \triangleq\left(\text{zip}\bef g^{\uparrow}\right)\left(q_{1}\times q_{2}\right)\\
\text{fmap}_{2}\,g^{A\times B\rightarrow C} & \triangleq\text{zip}\bef g^{\uparrow}
\end{align*}
}{\footnotesize\par}
\item Combine the two naturality laws into one by using two functions $f_{1}$,
$f_{2}$:{\footnotesize{}
\begin{align*}
\left(f_{1}^{\uparrow}\otimes f_{2}^{\uparrow}\right)\bef\text{fmap2}\,g & =\text{fmap2}\left(\left(f_{1}\otimes f_{2}\right)^{\uparrow}\bef g\right)\\
\left(f_{1}^{\uparrow}\otimes f_{2}^{\uparrow}\right)\bef\text{zip}\bef g^{\uparrow} & =\text{zip}\bef\left(f_{1}\otimes f_{2}\right)^{\uparrow}\bef g^{\uparrow}
\end{align*}
}{\footnotesize\par}
\item \vspace{-0.2cm}The \textbf{naturality law} for \texttt{\textcolor{blue}{\footnotesize{}zip}}
then becomes: {\footnotesize{}$\left(f_{1}^{\uparrow}\otimes f_{2}^{\uparrow}\right)\bef\text{zip}=\text{zip}\bef\left(f_{1}\otimes f_{2}\right)^{\uparrow}$} 
\end{itemize}
\end{itemize}


\paragraph{Deriving the laws for \texttt{\textcolor{blue}{\footnotesize{}zip}}:
associativity law}
\begin{itemize}
\item Express \texttt{\textcolor{blue}{\footnotesize{}map2}} through \texttt{\textcolor{blue}{\footnotesize{}zip}}
and substitute into the associativity law:{\footnotesize{}
\[
g_{1.23}^{\uparrow}\left(\text{zip}\left(q_{1}\times\text{zip}\left(q_{2}\times q_{3}\right)\right)\right)=g_{12.3}^{\uparrow}\left(\text{zip}\left(\text{zip}\left(q_{1}\times q_{2}\right)\times q_{3}\right)\right)
\]
}{\footnotesize\par}
\begin{itemize}
\item The arbitrary function $g$ is preceded by transformations of the
tuples,{\footnotesize{}
\[
a\times\left(b\times c\right)\triangleq\left(a\times b\right)\times c\quad\text{(type isomorphism)}
\]
}{\footnotesize\par}
\item Assume that the isomorphism transformations are applied as needed,
then we may formulate the \textbf{associativity law} for \texttt{\textcolor{blue}{\footnotesize{}zip}}
more concisely:{\footnotesize{}
\[
\text{zip}\left(\text{zip}\left(q_{1}\times q_{2}\right)\times q_{3}\right)\cong\text{zip}\left(q_{1}\times\text{zip}\left(q_{2}\times q_{3}\right)\right)
\]
}\vspace{-0.2cm}
\[
\xymatrix{\xyScaleY{1.4pc}\xyScaleX{3pc}F^{\left(A\times B\right)\times C}\ar[r] & F^{A\times B\times C}\ar[r]\ar[l] & F^{A\times\left(B\times C\right)}\ar[l]\\
F^{A\times B}\times F^{C}\ar[u]\sp(0.6){\text{zip}} & F^{A}\ar[ldd]\ar[r] & F^{A}\times F^{B\times C}\ar[u]\sb(0.6){\text{zip}}\\
F^{A\times B}\ar[u] & F^{C}\ar[rd]\ar[lu] & F^{B\times C}\ar[u]\\
F^{A}\times F^{B}\ar[u]\sp(0.6){\text{zip}} & F^{B}\ar[r]\ar[l] & F^{B}\times F^{C}\ar[u]\sb(0.6){\text{zip}}
}
\]
\end{itemize}
\end{itemize}


\paragraph{Deriving the laws for \texttt{\textcolor{blue}{\footnotesize{}zip}}:
identity laws}
\begin{itemize}
\item \vspace{-0.2cm}Identity laws seem to be complicated, e.g.\ the left
identity:{\footnotesize{}
\[
g^{\uparrow}\left(\text{zip}\left(\text{pure}\,a\times q\right)\right)=\left(b\rightarrow g\left(a\times b\right)\right)^{\uparrow}q
\]
}{\footnotesize\par}
\begin{itemize}
\item Replace \texttt{\textcolor{blue}{\footnotesize{}pure}} by an \emph{equivalent}
\textsf{``}wrapped unit\textsf{''} method \texttt{\textcolor{blue}{\footnotesize{}wu:\ F{[}Unit{]}}}{\footnotesize{}
\[
\text{wu}^{F^{1}}\triangleq\text{pure}\left(1\right);\quad\text{pure}(a^{A})=\left(1\rightarrow a\right)^{\uparrow}\text{wu}
\]
}Then the left identity law can be simplified using left naturality:{\footnotesize{}
\[
g^{\uparrow}\left(\text{zip}\left((\left(1\rightarrow a\right)^{\uparrow}\text{wu})\times q\right)\right)=g^{\uparrow}\left(\left((1\rightarrow a)\otimes\text{id}\right)^{\uparrow}\text{zip}\left(\text{wu}\times q\right)\right)
\]
}{\footnotesize\par}
\item Denote {\footnotesize{}$\phi^{B\rightarrow1\times B}\triangleq b\rightarrow1\times b$}
and {\footnotesize{}$\beta_{a}^{1\times B\rightarrow A\times B}\triangleq\left(1\rightarrow a\right)\otimes\text{id}$};
then the function {\footnotesize{}$b\rightarrow g\left(a\times b\right)$}
can be expressed more simply as {\footnotesize{}$\phi\bef\beta_{a}\bef g$},
and the identity law becomes{\footnotesize{}
\[
g^{\uparrow}(\beta_{a}^{\uparrow}\,\text{zip}\left(\text{wu}\times q\right))=\left(\beta_{a}\bef g\right)^{\uparrow}\left(\text{zip}\left(\text{wu}\times q\right)\right)=\left(\phi\bef\beta_{a}\bef g\right)^{\uparrow}q=\left(\beta_{a}\bef g\right)^{\uparrow}(\phi^{\uparrow}q)
\]
}Omitting the common prefix {\footnotesize{}$\left(\beta_{a}\bef g\right)^{\uparrow}$},
we obtain the \textbf{left identity} law:{\footnotesize{}
\[
\text{zip}\left(\text{wu}\times q\right)=\phi^{\uparrow}q
\]
}{\footnotesize\par}
\begin{itemize}
\item Note that $\phi^{\uparrow}$ is an isomorphism between $F^{B}$ and
$F^{1\times B}$
\begin{itemize}
\item Assume that this isomorphism is applied as needed, then we may write{\footnotesize{}
\[
\text{zip}\left(\text{wu}\times q\right)\cong q
\]
}{\footnotesize\par}
\end{itemize}
\item Similarly, the \textbf{right identity} law can be written as {\footnotesize{}$\text{zip}\left(q\times\text{wu}\right)\cong q$}{\footnotesize\par}
\end{itemize}
\end{itemize}
\end{itemize}


\paragraph{Similarity between applicative laws and monoid laws}
\begin{itemize}
\item Define infix syntax for \texttt{\textcolor{blue}{\footnotesize{}zip}}
and write $\text{zip}\left(p\times q\right)\triangleq p\bowtie q$
\begin{itemize}
\item Then the associativity and identity laws may be written as{\footnotesize{}
\begin{align*}
q_{1}\bowtie\left(q_{2}\bowtie q_{3}\right) & \cong\left(q_{1}\bowtie q_{2}\right)\bowtie q_{3}\\
\left(\text{wu}\,\bowtie q\right) & \cong q\\
\left(q\bowtie\text{wu}\right) & \cong q
\end{align*}
}These are the laws of a monoid (with some assumed transformations)
\item Naturality law for \texttt{\textcolor{blue}{\footnotesize{}zip}} written
in the infix syntax:{\footnotesize{}
\[
f_{1}^{\uparrow}q_{1}\bowtie f_{2}^{\uparrow}q_{2}=\left(f_{1}\otimes f_{2}\right)^{\uparrow}\left(q_{1}\bowtie q_{2}\right)
\]
}{\footnotesize\par}
\item \texttt{\textcolor{blue}{\footnotesize{}wu}} has no laws; the naturality
for \texttt{\textcolor{blue}{\footnotesize{}pure}} follows automatically
\item The laws are simplest when formulated in terms of \texttt{\textcolor{blue}{\footnotesize{}zip}}
and \texttt{\textcolor{blue}{\footnotesize{}wu}} 
\begin{itemize}
\item Naturality for \texttt{\textcolor{blue}{\footnotesize{}zip}} will
usually follow from parametricity
\begin{itemize}
\item A third naturality law for \texttt{\textcolor{blue}{\footnotesize{}map2}}
follows from defining \texttt{\textcolor{blue}{\footnotesize{}map2}}
through \texttt{\textcolor{blue}{\footnotesize{}zip}}!
\end{itemize}
\end{itemize}
\item \textsf{``}Zippable\textsf{''} functors have only the associativity and naturality
laws
\item Applicative functors are a strict superset of monadic functors
\begin{itemize}
\item There are applicative functors that \emph{cannot} be monads
\item Applicative functor implementation may disagree with the monad
\end{itemize}
\end{itemize}
\end{itemize}


\paragraph{A third naturality law for \texttt{\textcolor{blue}{\footnotesize{}map2}} }
\begin{itemize}
\item \vspace{-0.1cm}There must be one more naturality law for \texttt{\textcolor{blue}{\footnotesize{}map2}} 
\begin{itemize}
\item Transform the result of a \texttt{\textcolor{blue}{\footnotesize{}map2}}:\texttt{\textcolor{blue}{\footnotesize{}\smallskip{}
}}{\footnotesize\par}
\end{itemize}
\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}(~for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~g(x,~y)~~).map(f)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~cont2}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~f(~g(x,~y)~)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}
\begin{itemize}
\item Write this in terms of \texttt{\textcolor{blue}{\footnotesize{}map2}},
obtain a third naturality law:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}map2(cont1,~cont2)(g).map(f)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~=~map2(cont1,~cont2)(g~andThen~f)}{\footnotesize{}
\begin{align*}
\text{fmap}2\left(g\right)\bef f^{\uparrow} & =\text{fmap2}\left(g\bef f\right)\\
f^{\uparrow}\left(\text{fmap}2\left(g\right)\left(p\times q\right)\right) & =\text{fmap2}\left(g\bef f\right)\left(p\times q\right)
\end{align*}
}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item This law automatically follows if we define \texttt{\textcolor{blue}{\footnotesize{}map2}}
through \texttt{\textcolor{blue}{\footnotesize{}zip}}:{\footnotesize{}
\[
\text{fmap}2\left(g\right)\bef f^{\uparrow}=\text{zip}\bef g^{\uparrow}\bef f^{\uparrow}=\text{zip}\bef\left(g\bef f\right)^{\uparrow}
\]
}{\footnotesize\par}
\item Note: We always have one naturality law per type parameter
\end{itemize}
\end{itemize}


\paragraph{Applicative operation \texttt{\textcolor{blue}{\footnotesize{}ap}}
as a \textsf{``}lifting\textsf{''}}
\begin{itemize}
\item \vspace{-0.18cm}Consider \texttt{\textcolor{blue}{\footnotesize{}ap}}
as a \textsf{``}lifting\textsf{''} since it has type{\footnotesize{} $F^{A\rightarrow B}\rightarrow\left(F^{A}\rightarrow F^{B}\right)$}{\footnotesize\par}
\begin{itemize}
\item A \textsf{``}lifting\textsf{''} should obey the identity and the composition laws
\begin{itemize}
\item An \textsf{``}identity\textsf{''} value of type $F^{A\rightarrow A}$, mapped to $\text{id}^{F^{A}\rightarrow F^{A}}$
by \texttt{\textcolor{blue}{\footnotesize{}ap}} 
\begin{itemize}
\item A good candidate for that value is $\text{id}_{\odot}\triangleq\text{pure}\left(\text{id}^{A\rightarrow A}\right)$
\end{itemize}
\item A \textsf{``}composition\textsf{''} of an $F^{A\rightarrow B}$ and an $F^{B\rightarrow C}$,
yielding an $F^{A\rightarrow C}$
\begin{itemize}
\item We can use \texttt{\textcolor{blue}{\footnotesize{}map2}} to implement
this composition, denoted $g\odot h$:
\[
g^{F^{A\rightarrow B}}\odot h^{F^{B\rightarrow C}}\triangleq\text{fmap2}\,(p^{A\rightarrow B}\times q^{B\rightarrow C}\rightarrow p\bef q)\left(g,h\right)
\]
\end{itemize}
\end{itemize}
\item What are the laws that follow for $g\odot h$ from the \texttt{\textcolor{blue}{\footnotesize{}map2}}
laws?{\footnotesize{}
\begin{align*}
\text{id}_{\odot}\odot h=h; & \quad g\odot\text{id}_{\odot}=g\\
g^{F^{A\rightarrow B}}\odot(h^{F^{B\rightarrow C}}\odot k^{F^{C\rightarrow D}}) & =\left(g\odot h\right)\odot k\\
\left((x^{B\rightarrow C}\rightarrow f^{A\rightarrow B}\bef x)^{\uparrow}g^{F^{B\rightarrow C}}\right)\odot h^{F^{C\rightarrow D}} & =(x^{B\rightarrow D}\rightarrow f^{A\rightarrow B}\bef x)^{\uparrow}\left(g\odot h\right)\\
g^{F^{A\rightarrow B}}\odot\left((x^{B\rightarrow C}\rightarrow x\bef f^{C\rightarrow D})^{\uparrow}h^{F^{B\rightarrow C}}\right) & =(x^{A\rightarrow C}\rightarrow x\bef f^{C\rightarrow D})^{\uparrow}\left(g\odot h\right)
\end{align*}
}{\footnotesize\par}
\begin{itemize}
\item The first 3 laws are the identity \& associativity laws of a \emph{category}
\begin{itemize}
\item The morphism type is $A\rightsquigarrow B\triangleq F^{A\rightarrow B}$,
the composition is $\odot$
\end{itemize}
\item The last 2 laws are naturality laws, connecting $\text{fmap}$ and
$\odot$
\end{itemize}
\item Therefore \texttt{\textcolor{blue}{\footnotesize{}ap}} is a functor\textsf{'}s
\textsf{``}lifting\textsf{''} of morphisms from two categories
\end{itemize}
\end{itemize}


\paragraph{Deriving the category laws for $\left(\text{id}_{\odot},\odot\right)$}

\vspace{-0.10cm}The five laws for $\text{id}_{\odot}$ and $\odot$
follow from the five \texttt{\textcolor{blue}{\footnotesize{}map2}}
laws
\begin{itemize}
\item Consider $\text{id}_{\odot}\odot h$ and substitute the definition
of $\odot$ via \texttt{\textcolor{blue}{\footnotesize{}map2}}, cf.\ slide
7: $\text{id}_{\odot}\odot h=\text{fmap2}\left(p\times q\rightarrow p\bef q\right)\left(\text{pure}\left(\text{id}\right)\times h\right)=\left(b\rightarrow\text{id}\bef b\right)^{\uparrow}h=h$
\begin{itemize}
\item The law $g\odot\text{id}_{\odot}=g$ is derived similarly
\item Associativity law: {\footnotesize{}$g\odot\left(h\odot k\right)=\text{fmap2}\left(\bef\right)\left(g\times\text{fmap2}\left(\bef\right)\left(h\times k\right)\right)$}
The 3rd naturality law gives:{\footnotesize{} $\text{fmap2}\left(\bef\right)\left(h\times k\right)=\left(\bef\right)^{\uparrow}\left(\text{fmap2}\left(\text{id}\right)\left(h\times k\right)\right)$},
and then:{\footnotesize{}
\begin{align*}
g\odot\left(h\odot k\right) & =\text{fmap2}\left(x\times\left(y\times z\right)\rightarrow x\bef y\bef z\right)\left(g\times\text{fmap2}\left(\text{id}\right)\left(h\times k\right)\right)\\
\left(g\odot h\right)\odot k & =\text{fmap2}\left(\left(x\times y\right)\times z\rightarrow x\bef y\bef z\right)\left(\text{fmap2}\left(\text{id}\right)\left(g\times h\right)\times k\right)
\end{align*}
}Now the associativity law for{\footnotesize{} $\text{fmap2}$ }yields
{\footnotesize{}$g\odot\left(h\odot k\right)=\left(g\odot h\right)\odot k$}{\footnotesize\par}
\item Derive naturality laws for $\odot$ from the three {\footnotesize{}$\text{map}_{2}$}
naturality laws: {\footnotesize{}$\left((x\rightarrow f\bef x)^{\uparrow}g\right)\odot h=\text{fmap2}\left(\bef\right)\left((x\rightarrow f\bef x)^{\uparrow}g\times h\right)=$
$\text{fmap2}\left(x\times y\rightarrow f\bef x\bef y\right)\left(g\times h\right)=\left(x\rightarrow f\bef x\right)^{\uparrow}\left(\text{fmap2}\left(\bef\right)\left(g\times h\right)\right)=\left(x\rightarrow f\bef x\right)^{\uparrow}\left(g\odot h\right)$}{\footnotesize\par}
\item The law is {\footnotesize{}$g\odot(x\rightarrow x\bef f)^{\uparrow}h=(x\rightarrow x\bef f)^{\uparrow}\left(g\odot h\right)$}
is derived similarly
\end{itemize}
\end{itemize}


\paragraph{Deriving the functor laws for \texttt{\textcolor{blue}{\footnotesize{}ap}} }

\vspace{-0.10cm}Now that we established the laws for $\odot$, we
have \texttt{\textcolor{blue}{\footnotesize{}ap}} laws:
\[
\text{ap}^{[B,Z]}:F^{B\rightarrow Z}\rightarrow F^{B}\rightarrow F^{Z}=\text{fmap}_{2}\left(\text{id}^{\left(B\rightarrow Z\right)\rightarrow\left(B\rightarrow Z\right)}\right)
\]

Identity law: $\text{ap}\left(\text{id}_{\odot}\right)=\text{id}^{F^{A}\rightarrow F^{A}}$
\begin{itemize}
\item Derivation:{\footnotesize{} $\text{ap}\,(\text{id}_{\odot}^{F^{A\rightarrow A}})\,(q^{F^{A}})=\text{fmap}_{2}(\text{id}^{\left(A\rightarrow A\right)\rightarrow A\rightarrow A})\,(\text{pure}\,(\text{id}^{A\rightarrow A}))\,(q^{F^{A}})=$}
{\footnotesize{}$\text{fmap2}\left(f\times x\rightarrow f(x)\right)\left(\text{pure}\left(\text{id}\right)\times q\right)=$
$\left(x\rightarrow\text{id}(x)\right)^{\uparrow}q=\text{id}^{\uparrow}q=q$} 
\begin{itemize}
\item Easier derivation: first, express {\footnotesize{}$\text{ap}$} via
$\odot$ using the isomorphisms{\footnotesize{}
\[
A\cong1\rightarrow A;\quad F^{A}\cong F^{1\rightarrow A}
\]
}Then {\footnotesize{}$\text{ap}\,(p^{F^{B\rightarrow Z}})\,(q^{F^{B}})\cong q^{F^{1\rightarrow B}}\odot p^{F^{B\rightarrow Z}}$}
and so {\footnotesize{}$\text{ap}\left(\text{id}_{\odot}\right)\left(q\right)\cong q\odot\text{id}_{\odot}=q$}{\footnotesize\par}
\end{itemize}
Composition law: $\text{ap}\left(g\odot h\right)=\text{ap}\left(g\right)\bef\text{ap}\left(h\right)$
\begin{itemize}
\item Derivation: use $\text{ap}\,p\,q\cong q\odot p$ to get {\footnotesize{}$\text{ap}\left(g\odot h\right)\left(q\right)\cong q\odot\left(g\odot h\right)$}
while {\footnotesize{}$\left(\text{ap}\left(g\right)\bef\text{ap}\left(h\right)\right)q=$
$\text{ap}\left(h\right)\left(\text{ap}\left(g\right)\left(q\right)\right)\cong\text{ap}\left(h\right)\left(q\odot g\right)\cong\left(q\odot g\right)\odot h$}{\footnotesize\par}
\end{itemize}
\end{itemize}


\paragraph{Constructions of applicative functors}
\begin{itemize}
\item \vspace{-0.10cm}All monadic constructions still hold for applicative
functors
\begin{itemize}
\item Additionally, there are some non-monadic constructions
\end{itemize}
\begin{enumerate}
\item $F^{A}\triangleq1$ (constant functor) and $F^{A}\triangleq A$ (identity
functor)
\item $F^{A}\triangleq G^{A}\times H^{A}$ for any applicative $G^{A}$
and $H^{A}$
\begin{itemize}
\item but $G^{A}+H^{A}$ is in general \emph{not} applicative
\end{itemize}
\item $F^{A}\triangleq A+G^{A}$ for any applicative $G^{A}$ (\textbf{free
pointed} over $G$)
\item $F^{A}\triangleq A+G^{F^{A}}$ (recursive) for \emph{any} functor
$G^{A}$ (\textbf{free monad} over $G$)
\item $F^{A}\triangleq H^{A}\rightarrow A$ for \emph{any} contrafunctor
$H^{A}$\\
Constructions that do not correspond to monadic ones:
\item $F^{A}\triangleq Z$ (constant functor, $Z$ a monoid)
\item $F^{A}\triangleq Z+G^{A}$ for any applicative $G^{A}$ and monoid
$Z$
\item $F^{A}\triangleq G^{H^{A}}$ when both $G$ and $H$ are applicative
\end{enumerate}
\begin{itemize}
\item Applicative that disagrees with its monad: $F^{A}\triangleq1+\left(1\rightarrow A\times F^{A}\right)$ 
\item Examples of non-applicative functors: $F^{A}\triangleq\left(P\rightarrow A\right)+\left(Q\rightarrow A\right)$,
$F^{A}\triangleq\left(A\rightarrow P\right)\rightarrow Q$,\  $F^{A}\triangleq\left(A\rightarrow P\right)\rightarrow1+A$
\end{itemize}
\end{itemize}


\paragraph{All non-parameterized exp-poly types are monoids}
\begin{itemize}
\item \vspace{-0.1cm}Using known monoid constructions (Chapter\ 7), we
can implement $X+Y$, $X\times Y$, $X\rightarrow Y$ as monoids when
$X$ and $Y$ are monoids

By constructions 1, 2, 6, 7, \emph{all} polynomial $F^{A}$ with monoidal
coefficients are applicative: write $F^{A}=Z_{1}+A\times\left(Z_{2}+A\times...\right)$
with some monoids $Z_{i}$
\begin{itemize}
\item Examples: $F^{A}=1+A\times A$ (this $F^{A}$ cannot be a monad!)
\item $F^{A}=A+A\times A\times Z$ where $Z$ is a monoid (this $F^{A}$
is a monad)
\end{itemize}
Previous examples of non-applicative functors are all \emph{non-polynomial}
\end{itemize}


\paragraph{Definition and constructions of applicative contrafunctors}
\begin{itemize}
\item \vspace{-0.25cm}The applicative functor laws, if formulated via \texttt{\textcolor{blue}{\footnotesize{}zip}}
and \texttt{\textcolor{blue}{\footnotesize{}wu}}, do not use \texttt{\textcolor{blue}{\footnotesize{}map}}
and therefore can be formulated for contrafunctors
\begin{itemize}
\item Define an \textbf{applicative contrafunctor} $C^{A}$ as having \texttt{\textcolor{blue}{\footnotesize{}zip}}
and \texttt{\textcolor{blue}{\footnotesize{}wu}}:{\footnotesize{}
\[
\text{zip}:C^{A}\times C^{B}\rightarrow C^{A\times B};\quad\text{wu}:C^{1}
\]
}{\footnotesize\par}
\item Identity and associativity laws must hold for \texttt{\textcolor{blue}{\footnotesize{}zip}}
and \texttt{\textcolor{blue}{\footnotesize{}wu}} 
\begin{itemize}
\item Note: applying \texttt{\textcolor{blue}{\footnotesize{}contramap}}
to the function $a\times b\rightarrow a$ will yield some $C^{A}\rightarrow C^{A\times B}$,
but this will \emph{not} give a valid implementation of \texttt{\textcolor{blue}{\footnotesize{}zip}}!
\end{itemize}
\item Naturality must hold for \texttt{\textcolor{blue}{\footnotesize{}zip}},
but with \texttt{\textcolor{blue}{\footnotesize{}contramap}} instead
of \texttt{\textcolor{blue}{\footnotesize{}map}} 
\begin{itemize}
\item There are no corresponding \texttt{\textcolor{blue}{\footnotesize{}pure}}
or \texttt{\textcolor{blue}{\footnotesize{}contraap}}! But have $\text{cpure}:\forall A:C^{A}$
\end{itemize}
\end{itemize}
Applicative contrafunctor constructions:
\begin{enumerate}
\item $C^{A}\triangleq Z$ (constant functor, $Z$ a monoid)
\item $C^{A}\triangleq G^{A}\times H^{A}$ for any applicative contrafunctors
$G^{A}$ and $H^{A}$
\item $C^{A}\triangleq G^{A}+H^{A}$ for any applicative contrafunctors
$G^{A}$ and $H^{A}$
\item $C^{A}\triangleq H^{A}\rightarrow G^{A}$ for \emph{any} \emph{functor}
$H^{A}$ and applicative contrafunctor $G^{A}$
\item $C^{A}\triangleq G^{H^{A}}$ if a functor $G^{A}$ and contrafunctor
$H^{A}$ are both applicative
\end{enumerate}
\begin{itemize}
\item \emph{All} exponential-polynomial contrafunctors with monoidal coefficients
are applicative! (These constructions cover all exp-poly cases.)
\end{itemize}
\end{itemize}


\paragraph{Definition and laws of profunctors}
\begin{itemize}
\item \textbf{Profunctors} have the type parameter in both contravariant
and covariant positions; they can have neither \texttt{\textcolor{blue}{\footnotesize{}map}}
nor \texttt{\textcolor{blue}{\footnotesize{}contramap}} 
\begin{itemize}
\item Examples of profunctors: {\footnotesize{}$P^{A}\triangleq\bbnum 1+\text{Int}\times A\rightarrow A$;
$P^{A}\triangleq A+\left(A\rightarrow\text{String}\right)$}{\footnotesize\par}
\item Example of non-profunctor: a GADT, {\footnotesize{}$F^{A}\triangleq\text{String}^{:F^{\text{Int}}}+\text{Int}^{:F^{\bbnum 1}}$}{\footnotesize\par}
\end{itemize}
\end{itemize}


\paragraph{Definition and constructions of applicative profunctors}
\begin{itemize}
\item Definition of \textbf{applicative profunctor}: has \texttt{\textcolor{blue}{\footnotesize{}zip}}
and \texttt{\textcolor{blue}{\footnotesize{}wu}} with the laws
\begin{itemize}
\item There is no corresponding \texttt{\textcolor{blue}{\footnotesize{}ap}}!
But have \texttt{\textcolor{blue}{\footnotesize{}pure}} {\footnotesize{}$:A\rightarrow P^{A}$} 
\end{itemize}
Applicative profunctors admit all previous constructions, and in addition:
\begin{enumerate}
\item $P^{A}\triangleq G^{A}\times H^{A}$ for any applicative profunctors
$G^{A}$ and $H^{A}$
\item $P^{A}\triangleq Z+G^{A}$ for any applicative profunctor $G^{A}$
and monoid $Z$
\item $P^{A}\triangleq A+G^{A}$ for any applicative profunctor $G^{A}$
\item $P^{A}\triangleq F^{A}\rightarrow Q^{A}$ for \emph{any} \emph{functor}
$F^{A}$ and applicative profunctor $Q^{A}$
\begin{itemize}
\item Non-working construction: $P^{A}\triangleq H^{A}\rightarrow A$ for
a profunctor $H^{A}$
\end{itemize}
\item $P^{A}\triangleq G^{H^{A}}$ for a functor $G^{A}$ and a profunctor
$H^{A}$, both applicative
\end{enumerate}
\end{itemize}


\paragraph{Commutative applicative functors}
\begin{itemize}
\item \vspace{-0.15cm}The monoidal operation $\oplus$ can be \textbf{commutative}
w.r.t.\ its arguments:{\footnotesize{}
\[
x\oplus y=y\oplus x
\]
}{\footnotesize\par}
\begin{itemize}
\item Applicative operation \texttt{\textcolor{blue}{\footnotesize{}zip}}
can be \textbf{commutative} w.r.t.\ its arguments:{\footnotesize{}
\[
\left(a\times b\rightarrow b\times a\right)^{\uparrow}\left(fa\bowtie fb\right)=fb\bowtie fa
\]
}or $fa\bowtie fb\cong fb\bowtie fa$, implicitly using the isomorphism
$a\times b\rightarrow b\times a$
\item Applicative functor is commutative if the second effect is independent
of the first effect (not only of the first value)
\item Examples:
\begin{itemize}
\item $\text{List}$ is commutative; applicative parsers are not
\item If defined through the monad instance, \texttt{\textcolor{blue}{\footnotesize{}zip}}
is usually not commutative
\item All polynomial functors with \emph{commutative} monoidal coefficients
are commutative applicative functors 
\end{itemize}
\item Most applicative constructions preserve commutativity 
\item The same applies to applicative contrafunctors and profunctors 
\item Commutativity makes proving associativity easier: {\footnotesize{}
\[
\left(fa\bowtie fb\right)\bowtie fc\cong fc\bowtie\left(fb\bowtie fa\right)
\]
}so it\textsf{'}s sufficient to swap $fa$ and $fc$ and show equivalence
\end{itemize}
\end{itemize}


\paragraph{Categorical overview of \textsf{``}regular\textsf{''} functor classes}

The \textsf{``}liftings\textsf{''} show the types of category\textsf{'}s morphisms
\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\scriptsize{}class name} & \textbf{\scriptsize{}lifting\textsf{'}s name and type signature} & \textbf{\scriptsize{}category\textsf{'}s morphism}\tabularnewline
\hline 
\hline 
{\scriptsize{}functor} & {\scriptsize{}$\text{fmap}:\left(A\rightarrow B\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$A\rightarrow B$}\tabularnewline
\hline 
{\scriptsize{}filterable} & {\scriptsize{}$\text{liftOpt}:\left(A\rightarrow1+B\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$A\rightarrow1+B$}\tabularnewline
\hline 
{\scriptsize{}monad} & {\scriptsize{}$\text{flm}:\left(A\rightarrow F^{B}\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$A\rightarrow F^{B}$}\tabularnewline
\hline 
{\scriptsize{}applicative} & {\scriptsize{}$\text{ap}:F^{A\rightarrow B}\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$F^{A\rightarrow B}$}\tabularnewline
\hline 
{\scriptsize{}contrafunctor} & {\scriptsize{}$\text{cmap}:\left(B\rightarrow A\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$B\rightarrow A$}\tabularnewline
\hline 
{\scriptsize{}profunctor} & {\scriptsize{}$\text{xmap}:\left(A\rightarrow B\right)\times\left(B\rightarrow A\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$\left(A\rightarrow B\right)\times\left(B\rightarrow A\right)$}\tabularnewline
\hline 
{\scriptsize{}contra-filterable} & {\scriptsize{}$\text{liftOpt}:\left(B\rightarrow1+A\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$B\rightarrow1+A$}\tabularnewline
\hline 
\multicolumn{1}{|c}{} & \multicolumn{1}{c}{{\scriptsize{}Not yet considered:}} & \tabularnewline
\hline 
{\scriptsize{}comonad} & {\scriptsize{}$\text{coflm}:\left(F^{A}\rightarrow B\right)\rightarrow F^{A}\rightarrow F^{B}$} & {\scriptsize{}$F^{A}\rightarrow B$}\tabularnewline
\hline 
\end{tabular}
\par\end{center}

Need to define each category\textsf{'}s composition and identity morphism

Then impose the category laws, the naturality laws, and the functor
laws
\begin{itemize}
\item Obtained a systematic picture of the \textsf{``}regular\textsf{''} type classes
\begin{itemize}
\item Some classes (e.g.\ contra-applicative) aren't covered by this scheme
\item Some of the possibilities (e.g.\ \textsf{``}contramonad\textsf{''}) don't actually
work out
\end{itemize}
\end{itemize}


\subsection{Exercises}
\begin{enumerate}
\item Show that \lstinline!pure! will be automatically a natural transformation
when it is defined using \lstinline!wu! as shown in Section{*}{*}{*}.
\item Use naturality of \lstinline!pure! to show that $\text{pu}_{L}(f)\odot\text{pu}_{L}(g)=\text{pu}_{L}\left(f\bef g\right)$
for an applicative functor $L$.
\item Show that $F^{A}\triangleq\left(A\rightarrow Z\right)\rightarrow\bbnum 1+A$
is a functor but not applicative.
\item Show that $P^{S}$ is a monoid if $S$ is a monoid and $P$ is any
applicative functor, contrafunctor, or profunctor.
\item Implement an applicative instance for $F^{A}=\bbnum 1+\text{Int}\times A+A\times A\times A$.
\item Using applicative constructions, show (without need for verifying
laws) that $F^{A}=G^{A}+H^{G^{A}}$ is applicative if $G$ and $H$
are applicative functors.
\item Explicitly implement contrafunctor construction 2 and prove the laws.
\item For any contrafunctor $H^{A}$, construction 5 says that $F^{A}\triangleq H^{A}\rightarrow A$
is applicative. Implement the code of zip(fa, fb) for this construction.
\item Show that the recursive functor $F^{A}\triangleq\bbnum 1+G^{A\times F^{A}}$
is applicative if $G^{A}$ is applicative and $\text{wu}_{F}$ is
defined recursively as $0+\text{pure}_{G}\left(1\times\text{wu}_{F}\right)$.
\item Explicitly implement profunctor construction 5 and prove the laws. 
\item Prove rigorously that all exponential-polynomial type constructors
are profunctors.
\item Implement profunctor and applicative instances for $P^{A}\triangleq A+Z\times G^{A}$
where $G^{A}$ is a given applicative profunctor and $Z$ is a monoid.
\item Show that, for any profunctor $P^{A}$, one can implement a function
of type $A\rightarrow P^{B}\rightarrow P^{A\times B}$ but not of
type $A\rightarrow P^{B}\rightarrow P^{A}$. 
\end{enumerate}

\section{Practical use}

\paragraph{Discussion}

\begin{comment}
this is chapter eight devoted to applicative hunters and pro functors
the first part will be practical examples main motivation for applicati
factors comes from considering kinetic computations or computations
in the factor block as I color in case when effects are independent
and competitive or in case when these effects could be executed in
parallel while the result is still correct here is an example consider
a portion of a functor block or a for yield block in Scala that looks
like this there are three future values and X will be waiting until
with this future value is ready imagine that these are some long-running
computations and after these three lines we can use XYZ and further
computations any further computations will be waiting for these three
futures now if we write code like this then these three futures will
be created sequentially that is first this future will be created
and scheduled on some thread and then when it\textsf{'}s done you get the value
X and then this second future will be created and scheduled even though
it doesn't use the value X but the monadic block or the for yield
block or the Thunder block whatever you want to call it I call it
a factor block the Thunder block is such that every generator line
locks everything else until it\textsf{'}s done so in the future we'll be created
one at a time and so obviously this is not optimal if you translate
this into flat map code and map that\textsf{'}s the code so you have a first
future but to which you append this flat map so you schedule it is
further computation only when the first computation is ready the second
future will be then started and this will be waiting until the second
future is ready and then the third future will be started and this
will be ready will be waiting until the third future is ready clearly
this is not optimal would like to parallelize these things and we
have seen in a previous tutorial that a very easy way of paralyzing
such computations is to create the futures before starting the factor
block but this is actually a specific feature of scholar where futures
already start computing when you create them there is no separate
method to start computing them which is actually a design flaw and
we would like to express more carefully that certain computations
can be done in parallel because they're independent whereas other
computations really have to wait one for another now in this example
like I said C 1 C 2 and C 3 are just some fixed computations that
don't depend on the values computed previously if we do have this
dependency and of course there\textsf{'}s no way except wait until each previous
computation is done but in case they're they're independent we would
like to be able to compute them in parallel and we would like to express
that in a better way you know code rather than just a hacky way where
you create these futures separately and then put into some variables
and then you write this code because that will work for future will
not work for some other factor another use case where moon ads or
monadic effects are not exactly what we want is a case when we perform
computations that may give errors now we have seen in the previous
chapter that using a moon ad such as either moon ad option will not
we could stop at the first error very easily but sometimes we don't
want to stop at the first error we want to maybe accumulate all errors
as much as possible and give the user more information so {[}Music{]}
monads cannot do that in general they cannot accumulate all errors
because if one monadic step fails then the next one won't be executed
so if as I said effects are independent then we would like to have
a different way of computing than the moon at computation shown here
so monads are inconvenient for expressing independent effects also
they're inconvenient for expressing commutative effects because typically
when you change the order of generator lines like these two you change
the results even though these generator lines seem to be independent
of each other they aren't the computation will first iterate with
X going over this list and for each X Y it will be going through that
list in that order first X will be iterated over in this list then
Y over that list now order is fixed and you can do nothing to change
it so for example if you interchange these two lines you would get
a different list as a result the first iteration would be interchange
with the second one and the list will have a different value now for
lists the order of the order of elements is important perhaps for
other monads usually this is also the case that you cannot just interchange
lines in a factor block and expect the result not to change however
there are some cases where these computations logically speaking are
independent and what we would like to do is express this very clearly
this is how it is done we would like to have a function that computes
something like this but assuming that the effects are commutative
how would that function work well look at what it does we have here
two containers and we compute some function from values that are stored
in these two containers and put all the results in a new container
so if we just express this computation as a function that function
would have the following type signature it will take two containers
let\textsf{'}s call them FA and FB so let\textsf{'}s say F is list and aliened b are
going to be the types of the elements in these two containers in this
example both integers but in general we might have two different types
a and B so this function takes these two containers it also takes
a function f which is a function from a pair a B to some type C as
a result we get a container of type C now clearly this kind of function
let\textsf{'}s call this map to because it\textsf{'}s like map except you have two containers
and two arguments of a function that you use now of course this computation
has this type signature so if you have a monad for F and then you
can define this function using this code very easily X left arrow
F a YF arrow left arrow FB yield F of x1 so that is the code that
implements map to in terms of flat map and map now the key observation
here is that we would like to not use the flat map because flat map
will force this ordering of effects and it will prevent us from having
commutative effects whereas this function we could define differently
we could define it separately from flat map in a different way such
that this function is symmetric in a and B for example we could do
that and once we are able to do that we can use that function by itself
without writing furniture blocks may be using a different syntax but
basically just using this function to prepare this data in this way
so to process several containers in a symmetric way that is to endure
more independent containers have independent effects and a function
that maps their values to some new type and the result is a new container
so that is the key idea behind applicative functors applicative factors
are factors F for which this function is available somehow also the
function P or the same function as in monads with the type signature
a going to f of a must be available but that function just like in
the case of Moonen is much less important for practical coding than
this function so applicative functor is a factor that has these but
first of all it does not have to be a monad and even if it is a monad
in some way the definition of map 2 does not have to come from the
definition of flat map like this so the reason is that we want a different
logic we don't want the calculation going like this with flat maps
we actually want to avoid using flat map so that\textsf{'}s why we would define
map 2 separately not via flat map and use that function map to directly
on some containers in this way for example we would be able to define
a function of three futures that takes also a function of three numbers
and compute the future of the result now that would be map 3 as it
were so let\textsf{'}s consider this as a generalization so as I said for a
monad we can define these functions through a flat map and let\textsf{'}s just
use that as a guide we're not going to define through flatmap really
but we should be able to get a lot of intuition by just looking at
the functions that we get from flat map because the types are going
to be the same and so a lot of intuition comes from looking at the
type of a function so if we just have one container then it\textsf{'}s a ordinary
map which is equivalent to this code in Scala I remind you that the
left arrow or the generator arrow is translated into either flat map
or map it\textsf{'}s if there are several generator arrows it\textsf{'}s the first until
the last one so the last but one all of them are flat maps and the
last one is map so the last left arrow before yield is just translated
into a map so that\textsf{'}s a map now this would be first a flat map than
an ordinary map but we want to replace that with this kind of syntax
perhaps where we have map - it takes a tuple of containers it also
takes a function f with two arguments and it returns a container here
is a similar thing with three containers where we have map three so
the function f needs to have three arguments and the result is again
a single container so how do we generalize this let\textsf{'}s write down the
type signatures so map the usual map let\textsf{'}s call it map one just to
be systematic then it\textsf{'}s like this this is the standard type signature
for the map function map to has this type signature takes two containers
as we already saw on the previous slide map three takes three containers
takes a function with three arguments instead of two and it again
returns a new container so clearly this is how we can generalize map
one map to map three and so on the type signatures are clear now applicative
factors have all of these functions map in in fact we will see in
a later tutorial that once you have map one and map two it is sufficient
in order to be able to define all the others you don't need to have
separate definitions for all the other maps in you can define map
in taking a list of these a list of these it\textsf{'}s easy once you have
met one and map - we will not dwell on it in this tutorial that\textsf{'}s
the subject of the next tutorial because it requires us to consider
the laws that must be satisfied by these map end functions and then
it will be much easier to understand why all these functions are interrelated
to each other but at the same time it will require us to go much deeper
into the relationships between these functions the equations and the
laws so that\textsf{'}s going to be the subject of the next tutorial part 2
of chapter 8 in this part one I'm just going to talk about practical
considerations practical examples of how you use this map in concentrating
mostly on map to map n will be used in a very similar way so what
are examples where we want to use such things let\textsf{'}s look at the example
code so the first example is the easier type so imagine we're doing
some computations when results could be given as values of type a
or as you could have a failure an error message that is represented
by a string an example of such a computation would be the safe divide
function where I divide but I check whether it is not 0 and if it\textsf{'}s
0 then I don't divide I'll give an error now this is just an example
of this kind of approach where your computations have the type up
of double instead of double and this is a type constructor that encapsulate
some effect some error accumulation or some other effect so in this
case this constructor represents errors usually as we have seen before
so let\textsf{'}s implement map 2 in a way that would help us understand how
we can collect all errors so map 2 needs to have this type signature
it takes up of a up of B it also takes a function from a B to Z and
it returns up of Z so it needs to have type parameters a B and Z how
do we compute this OP of Z well let\textsf{'}s find out we have up of a and
up of B now op is an either so we can imagine it let\textsf{'}s match right
away on both and the now that there\textsf{'}s a case when we have two errors
and in this case it will be interesting for us to accumulate these
error messages so let\textsf{'}s not throw away information here and let\textsf{'}s
do this so we can catenate the strings in more general situation this
type instead of string it could be some other type which could be
a monoid and then we could combine two values of a mono it into a
larger value in case we have one error and one result you can't really
do much except return that error and in case we have two results we
can actually perform a computation with this requesting which is this
function f and return a right so in these two cases there isn't enough
data to call F because we only have one value but not the other so
we cannot call F and the only thing we can return is an error so this
is how we implement map two now notice that this map 2 does more than
a monadic factor block would would do because the magnetic factor
block would stop after the first error this one doesn't stop not to
the first air it takes also look looks at the second computation and
if it also is an error then it accumulates the errors into into this
value this is something a monadic factor block cannot do cannot accumulate
errors because once it finds the first there it stops and returns
that error so here\textsf{'}s an example how we could compute for example here
is map - I'm just going to apply this function to the values you find
like this as an example now in a real computation this doesn't seem
to be very convenient to always have to write computations like this
Scala can give you a lot of convenience by defining domain-specific
language with syntax and operators so that you don't have to write
all that stuff but under the hood it must do this stuff so this is
the way it works under the hood for any kind of library that would
do this more conveniently so you could call this function map two-on-two
computations now notice they are both dividing by 0 so these two computations
will give you two error messages and now the function that you pass
is a subtraction and that function by itself doesn't give any errors
but it never gets called because you actually have errors in both
of these two computations so the tests asserts we actually have two
error messages telling you what you're dividing by zero now if you
instead wrote this kind of thing which has the same type signature
now you would have just one error message the first one would have
stopped the functor block from continuing so this is how it works
now we can define map three let\textsf{'}s take a look is a very simple type
can't be so bad now however we now have three computations each could
be an error or a result so there are eight possible cases we're not
going to write them down that would be really not great so how do
we do that well let\textsf{'}s think about how we could use map to instead
of writing this function map 3 from scratch map to only works by applying
it to two containers ok let\textsf{'}s do that let\textsf{'}s apply it to a and B and
well the function f requires three arguments we can't apply it let\textsf{'}s
not apply it let\textsf{'}s just apply it to some function that doesn't do
anything to the arguments just accumulate them in a tuple which is
almost an identity function just to remind you that in the Scala syntax
this is not actually a tuple this is anonymous function that takes
two arguments and if you wanted a tuple you'd have to write like this
which is the to pull of X while I'm going to the tuple of X Y this
is the actual identity function on tuples but this is not what we
defined so it\textsf{'}s almost an identity function up to some syntax we could
have defined the syntax so that it is really an identity so we don't
we just combine these two what\textsf{'}s the result the result is this so
it\textsf{'}s an oak of a tuple now we can use again map 2 to combine this
up of a tuple with C and then the map 2 will have this type of argument
now we can apply F so this kind of thing is how you could use me up
to to define map 3 now clearly this can be generalized a little awkward
to generalize but it can be generalized the awkwardness comes from
here it'll be hard to generalize this case expression obviously if
you have map n you need to apply map 2 then again map 2 again map
2 when you do that every time I have a more more 2 pulls in your case
expression so that\textsf{'}s a little awkward can be done with some more work
but not going to look at this right now yeah easier ways of defining
all these map and functions here is an example of how it works a map
3 working on three computations of this type accumulates the two errors
that you see the third computation does not give an error so that\textsf{'}s
fine now a use case for this kind of type is where you want to validate
value so imagine if has some case class with a few values you want
to you want to validate them and each validation is separate from
other validations just like each of these computations is separate
so only when all of the three parts of a tuple or a case class pass
validation you want to create actually a value of the case class otherwise
you want to fail but when you want when you fail you want to gather
all the errors this is how you would do that you would say you do
a map three of these three validated computations safe and divided
and then you would apply that map three on that to a function that
takes three values and maps and makes C case class value out of them
which is C don't apply no see don't apply is a function that takes
three arguments and returns case class I've made out of them so this
C dot apply is defined automatically by Scala very convenient so in
this case in this example obviously there aren't any divisions by
zero and so we get the result second so we have gone through these
two examples the third example is when we prefer a future our computations
concurrently and here\textsf{'}s how we would do that we would define lab 2
for futures now since these arguments are eagerly evaluated in there
there are already given when you call up to these futures already
were started on some threads and so we can just write the free on
block like we did before these futures are not really sequential because
they already have started so they run most likely on separate parallel
threads already when we are starting to evaluate this function so
that\textsf{'}s why it\textsf{'}s ok then you find map 2 through a flat map for futures
now that is a test when we do a map - like this on these two features
and then there\textsf{'}s another addition so it\textsf{'}s 1 + 2 3 + 4 3 that will
be 10 and map n can be defined like this so there\textsf{'}s a list of futures
and you returned the future of alistel doesn't really map in there
must be still a function so let\textsf{'}s call it something else in the standard
library it\textsf{'}s called future that sequence sequence is a kind of confusing
name it refers to changing of the order of these two type constructors
first you had a list of futures and then you have the future of the
list very important and useful function in the standard library that
essentially implements most of map in you still need to map this list
to some other value so the real map and we'll take a list of futures
they also take a function from a list of A to B so we need a type
of Z and we will return a future of B and the reason yeah and then
we would just do that in order to get it working so that was the example
of the futures another example where applicative factors could be
useful is when you have a reader mu net worth or functions with some
standard arguments and you are getting tired of passing these arguments
over and over to all kinds of functions so as we have seen in the
previous chapter the reader moment does that kind of thing and it
turns out that the reader monad whose effect is this constant value
D that you could always read which is kind of an standard argument
of all computations that you are doing now this e is a constant it
is an immutable given value and so and that\textsf{'}s the only effect of this
moment so this monad always has independent and commutative effects
so in this monad you don't have to worry about the order of effects
it is already independent and in other words we can define map to
buy a flat map there\textsf{'}s no penalty for doing so here\textsf{'}s an example imagine
we have some application that needs to use a logger now a logger we
will just do a quick and dirty logger which has a side effect which
takes whatever value of an any type and prints it in some way and
he returns unit now this is a very dirty way of doing login but it\textsf{'}s
quick it\textsf{'}s dirty in the sense that it\textsf{'}s hard to see that you have
logged anything or not because this function doesn't return any useful
values but let\textsf{'}s continue with that for now a functional logger of
this clean is the writer monad it tells you explicitly that there
is an extra value being created with each computation which is perhaps
a log message and it tells you also that you can bind the log messages
together using a Monod so that\textsf{'}s a clean way of logging but let\textsf{'}s
just for the sake of this example consider this logger so we have
an empty logger and maybe some non empty loggers and now suppose that
every computation we want is going to be logged so every computation
is going to use the slogger and call this print function many times
for whatever reason and so every computation needs a logger as an
argument because that logger will provide the printing functionality
and if you do that also it becomes much easier to test such code then
you can pass an empty lager or you can pass a test only debugging
lager or anything like that but then of course all your computations
become more cumbersome because now you have functions that have these
in this argument so here\textsf{'}s for example a computation that adds two
integers it returns a logged integer it is a function that takes a
logger it does this computation who logs it and returns the result
so it\textsf{'}s a typical kind of code that you would use now suppose I wanted
to combine these computations so I'm loading one plus two I'm logging
10 plus 20 the results are X\&Y and I have X plus y now changing the
order of computations gives the same result except for the side effect
printed of course that is not going to be commutative first it\textsf{'}s going
to print this and then it\textsf{'}s going to print that but the side effect
is invisible in the types of these expressions and so the expressions
are going to be equal after interchanging the order as this test shows
and this is another illustration of the bad nature of side effects
you don't see them you have no assurance that the side effects have
been performed in the order you want so for this example it will be
okay so now let\textsf{'}s define map to just define it via flat map like this
or we can define it by hand like this which is kind of obvious because
these this is a function from logger to a this is a function from
blogger to B and this is a function from logger to Z so we obviously
just call these two functions with a and B provided by those two functions
so echo F on this that\textsf{'}s the only way to implement map to now this
way is exactly the same actually we can verify this symbolically but
the code is exactly the same because maverick is this for the reader
munna flat map is that there\textsf{'}s no freedom here the types fix the code
uniquely and then we can calculate what is mapped to of a B which
is going to be this is this is the translation of the for yield construction
we can do that by first looking at the map substituting the definition
of the map right here and applying the function to the argument so
then you get this function and finally we need to put that function
into flat map substitute the definition of flat map which is this
and we get this code so by just symbolically transforming the code
I step-by-step arrive at the code of the other function so in this
way you could use map to map N and so on and have your standard arguments
passed to functions but so I do that with the reader Mona if you can
just do the for yield construction well what if you can't yeah there
is no Timon on somewhere in case your type is more complicated than
this you might be in a situation where you don't have a monad but
still you need to pass standard arguments and you can do that with
map in another example is the list which is a monad and we have seen
that every minute is already an applicative because you can always
define map to buy a flat map but there might be a different definition
map to in case of list there are various definitions we'll just use
a standard one right now and show how we can transpose a matrix so
let\textsf{'}s define map - first of all on map - is a very simple thing for
this is the zip so first we can zip see what we need is a function
from list a and list B - a list of pairs a B no look you just may
up with F and that\textsf{'}s what we write here so we do an a sub B which
gives us a list of pairs a B and we can map that now the zip function
has a specific implementation we could change that especially when
a and B do not have the same length then there are lots of choices
about what to do do you want to cut short so you want to fill with
some default values or something like that but what let\textsf{'}s not discuss
it right now we will see in in the second part of this tutorial how
to define map 2 in various ways in case there are several definitions
so for now we just use the standards library in Scala to have the
zip function so that\textsf{'}s clearly what map - does so you can see that
map 2 has a close connection to the zip function for lists that takes
two lists and returns a list of pairs and then you just map over that
list with a function f so in up to on a pair of these two lists with
a plus function will give you pairwise sums so how do we transpose
a matrix now the matrix represented here is a list of lists needs
to be transposed so in fact we need to understand how we represent
a {[}Music{]} matrix as list of lists so let me have a an example
so this matrix is a list of three lists and the transpose matrix is
a list of two lists but the first has these three elements together
and the second list has these three elements together so to transpose
them what we need is to take the heads of each list and put these
heads into a list of their own and then we can use transpose on the
tails of each list in the same way so we are we're going to have a
recursive function obviously so how do we do that so suppose that
this list of lists has heads and tails so what does it mean heads
so this is the heads now actually {[}Music{]} what you want is to
append this to this and to this you want to have a list that goes
like that so clearly the head of that list is going to be the head
of lips and let\textsf{'}s transpose the tails so tails are these so sorry
tails are these if we transpose them then we will have a list of these
two and then a list of these two now what we need to do is we need
to append this to that list and this to that list now this append
looks like a component wise operation on this list and on the list
of those so that\textsf{'}s where we use map to we use map to on heads which
is this and on transposed tails which is it transposed this to append
the first elements to the rest which means that we will append this
to that will append this to that and so on so it remains to transpose
the tails now it\textsf{'}s very easy to transpose the tails you just call
transpose on the tails right here everything else in this code is
bookkeeping that is designed carefully to avoid problems where you
have empty lists now that code is kind of cumbersome and error-prone
you do a map with a function that returns empty lists and here you
just return an empty list it took me a few tries to get it right this
code in this code but the other thing is more important so this is
how we use map tool in order to concatenate component-wise this with
this at the same time this with this and so on so this is the kind
of typical computation that the clickity factors do they do component
wise computations component wise computations are independent of each
other\textsf{'}s results so this is independent of this and that\textsf{'}s where you
use applicative factors and some tests to show that this is correct
so after these examples in principle there are a few other examples
where you use applicative factors and before going to those examples
that are a little more compact complicated I'd like to talk about
applicative contractors an applicative crew factors now the reason
I'm talking about this is that actually they are sometimes quite useful
you can have an applicative instance or a function such as map 2 or
zip for a tight constructor that is not a factor we have seen in a
previous tutorial that type constructors could fail to be factors
in a number of ways one of them is when they are contractors that
has contravariant type constructors but there\textsf{'}s another way where
they can be neither factors nor contra factors and that happens when
your type parameter is both in a covariant and in a contravariant
position in the type constructor sorry this is an example so if you
have a as your main type prime Z let\textsf{'}s say is a constant type it is
your main type parameter then this a is to the right of the function
arrow and this is to the left of the function area so this a and this
a are in a covariant position and this is in a contravariant position
because this type constructor contains both covariant and contravariant
position for a it cannot be a functor and it cannot be a control factor
for in terms of a but nevertheless it has still properties that are
quite nice it is called the true factor when you can see all type
parameters either in a covariant or in a contravariant position I
will talk about Pro factors later in more detail but for now just
keep in mind that it\textsf{'}s very easy to see which position is coherent
and which is controlling and just look at the function errors in your
type and everything to the left of a function arrow becomes contravariant
if there is an arrow inside that then it can again become covariant
so we have seen examples of this so here\textsf{'}s how Pro factors can become
useful this is an example where we can define a semigroup typeclass
instance for a type that has parts such as a tuple or a case class
where each part also has a semigroup typeclass instance and let\textsf{'}s
see how that works just for brevity I will define semigroup here like
this it\textsf{'}s a very simple tight class it just has one method and this
method basically is equivalent to this data type a product of two
S\textsf{'}s going to 1s so clearly this data type considered as a data type
is not a factor and not a control funky in the type parameter S now
we usually don't consider typeclass traits as containers as data types
but we can we could and what will happen if we do is we will notice
that usually there would not be factors and not become true factors
because they have too many things in both covariant and control positions
so these two are contravariant position this is a covariant position
but it is a pro functor because it has nothing but things in covariant
and contravariant positions in that case it\textsf{'}s going to be a pro factor
in fact all exponential polynomial types are going to be Pro factors
there\textsf{'}s no way you could fail to be be a profounder as long as your
stables and exponential polynomial types now the interesting thing
is that we could define a zip function for this type constructor so
let\textsf{'}s forget front at the moment that we're going to be using this
type constructor just to define a few implicit values for the typeclass
and let\textsf{'}s just consider that as a type constructor and try to see
what zip function would be for that type constructor well zip function
would have this signature we'll take one semi group another semi group
and we'll return a semi group of a pair how do we define that wallets
pretty straightforward you need to define a combined function that
combines a B and a B into a B or you just combine this a with this
a into this one and you combine this B with this B into this one using
the combine operation from the semigroups P\&Q and that\textsf{'}s the code
and now we can use that to define semi grouped typeclass instance
for a pair it\textsf{'}s just same I just I'm just going to use their syntax
and to test that this works i define semigroup instances for integer
and double in some way and i have a pair of int double and now I am
able to use the syntax so after this implicit definition I am able
to use this index so this is a zip function is very closely related
to map to we did not actually use map tool right now but once you
have zip then you get your container of pairs and all you need to
do is to map your function of two arguments over this container to
get the map tool so zip and map two are very closely related once
you implement one you can implement the other the second example I'd
like to give is that let\textsf{'}s consider this cofactor and let\textsf{'}s just implement
an app to for it now map to for a profounder has a different type
signature than map to for a factor and also it\textsf{'}s called imap2 in the
cat\textsf{'}s library and in any case to indicate that this is no this is
not a functor map to they call it invariant so prou factors are called
invariant which is quite confusing to me because invariant has so
many other meanings in different contexts such as how you make a transformation
but something doesn't change then you say something is invariant with
respect to the transformation but none of that is happening here nothing
is being transformed such that it remains invariant in geometry for
example the length of line segment is invariant under rotations the
the area of a triangle is invariant under rotations so that\textsf{'}s the
kind of context that I'm familiar with and calling this invariant
would lead me to to ask what is the transformation that you're applying
such that this does not change and that makes no sense at all in this
context or for instance in the computer science there is something
called loop invariant which is an expression that remains constant
throughout each iteration between each iterations of the loop there
is no loop here and nothing remains constant so again that meaning
of the word invariant does not apply so that\textsf{'}s confusing to me so
I don't want to talk about invariant factors I want to say Pro factors
it\textsf{'}s shorter anyway so let\textsf{'}s look at how we can implement an analogue
of map to function for this type constructor now this type constructor
as I said already it\textsf{'}s not a functor cannot be possibly in a factor
because it has the type parameter a in a contravariant position and
also in the covariant position so it cannot be a contra factor either
but it is nevertheless what I call zero ball you could define zip
for it and you can define imap2 for it let us see how do we define
i map to Fred so here I define this type constructor F now in order
to do an app - we use the function from a B to C and we applied that
to a container with a and container with D so here we have a container
with le here we have a container with B and here we have a function
from A to B to C but it turns out that\textsf{'}s insufficient you also need
a function from C back to a B only then it makes sense to define mapping
functions for a profounder and the reason is that when you want to
define a mapping function and you transform the type parameter say
a into some other type frame and say C but when you have your type
in a covariant position then you just compose with the function that
transforms when you have your type in a contravariant position you
have to have a function that goes backwards from C to a side and then
you would take a C you will use that function to get an A and when
you put that a as an argument in a contravariant position so for this
reason the profanity requires a function from C back to a B now if
this were purely a control factor then we would just use this function
from C to a B and we will be done I remind you that contra factors
are just very similar to functions except the map function takes the
opposite direction of transformation in types but here it is neither
a functor nor a contra factor and actually we need both functions
F and G F goes from a B to C and G goes from C back to an a B and
then it turns out we can do what we need how do we do that well so
let\textsf{'}s write the code being guided by types and by the intuition of
what we need to do so we need to produce an F of C and Z so that\textsf{'}s
going to be a function from Z C to C C so we need to return a tuple
of C see how do we do that well it\textsf{'}s obvious that we need to use these
functions F and G somehow we have a see if we use G on that we get
a pair of any bit let\textsf{'}s do that so we get some new a and new be my
back transforming C so now these new and new B need to be substituted
into the contravariant positions which are these positions so we take
F AZ and we substitute Z and a now Z there\textsf{'}s only one Z and that\textsf{'}s
not going to change if those are not transforming that type parameter
Z at all so Z stays the same but here we substitute new and new B
into the contravariant position of the F the result is going to be
pairs of a a and B B so let\textsf{'}s call them new a nu B B so now we can
apply F to this data to get a new value of C we need to have two different
values of C and it makes sense that we would use the first two and
the second to like that to substitute that into F so that\textsf{'}s how we
would do that let me try to improvise and define a zip function for
this type constructor so what would be a zip function so will be F
is e type fpz of type F of Z and the result will be F of pair a B
and Z Z is not going to change we're just by the transform and what
do I need I need type parameters a B and Z so how am I going to do
that well obviously F is this on e to have a function that takes Z
and a pair of a B in Scala I cannot just have a function that takes
that as arguments I need to do a case expression so that Ida structure
these arguments as it\textsf{'}s called or a match from them so now I need
to produce a pair of actually a B a B I need to return a pair of tuples
like that what I have is a function from za to a a and from Z B to
B so clearly I need to use those functions if I apply faz to Z and
a here I get an a a and it makes sense that I will put these days
here a and a and I'll do the same with B so let me write it down new
a a is fa z of new baby is f DZ of Z B so now I've got my Paris baby
and a and now I can return this which is going to be basically this
I'm going to return this Pinner and I'm going to return that pin now
if you compare this and the code appears to be quite similar except
that I don't have an F and I don't have a G and that\textsf{'}s quite typical
of these pairs of functions one of them is equal to the other when
we put identities instead of types instead of some arguments and the
other is obtained using some kind of F map so we've seen this pattern
before and that\textsf{'}s what it will be but that will be in the next part
of this tutorial so in this way we find that this kind of type constructor
has a zip like function which is exactly the same type signature is
a typical zip we'll begin with this if you ignore the extra type parameter
and will be just a typical zip F of a F of B going to F apparently
just like lists instead of f however this F is not a functor is a
much more difficult object perhaps to work with so that was that was
the example I was interested in showing how you can define zip and
imap2 for those profounder now and call non disjunctive and the reason
is these type expression do not contain any disjunctions and actually
if they do contain these junctions and it\textsf{'}s not always possible to
define zip so I call them zip herbal so not all of them are zip about
so it\textsf{'}s just a lot of them are but not all but when they do not contain
any disjunctions and they're always zip alone so with this understood
let us now consider an interesting practical case where we can use
this knowledge and actually make a code simpler in this case is the
so called fusion for fold and the idea is that fold is a computation
that iterates typically over a container and if you need to iterate
several times and then do a computation on the results that\textsf{'}s kind
of wasteful that\textsf{'}s better to iterate once and accumulate more intermediate
results but when you write code for this B it becomes cumbersome if
you have to do it every time you have to write a different complicated
fold function so the idea here is that we can actually automatically
merge several of these fold functions into one so that everything
is computed in one traversal so there are several libraries so one
library is called Scala fooled which is this one where this is implemented
where you can combine different folds of as an example I will show
you if you want to compute the average of a list then you'll have
to traverse the list twice once to define its length and another one
another time to make a summation and that\textsf{'}s wasteful and so you can
merge these folds into one so you can define a fold separately and
then apply merged merge several folds into one and apply that one
fold to a list traversing just once so let\textsf{'}s see how that works so
fold is an operation that takes several parameters so let\textsf{'}s remind
ourselves for instance a list the standard would be our running example
of data so hold left for instance what does it require requires an
initial value of some type B and an operation that takes the previous
accumulated value a new element of the list which is going to be of
type double and returns a new accumulated value so a fold essentially
takes these two values apply it when you apply that to the list so
let\textsf{'}s just have a type that encapsulates these two arguments over
fold left so this is going to be a very simple type just going to
be a tuple of these two values of this just like that so Z is the
type of values in your collection and R is a type of the result so
in order to call the full left you need to provide this data and the
list of course so let\textsf{'}s put this data into a type constructor of its
own so here I call it fold 0 so it\textsf{'}s kind of a 0 version of version
zero of this implementation I put it in Turkey\textsf{'}s class so the case
class is a product and I just put names on it for convenience and
very simple syntax extension will make it possible for us to apply
this fold value to a collection that is foldable now the foldable
typeclass we haven't looked at yet but basically just it\textsf{'}s a it\textsf{'}s
some items it\textsf{'}s a collection it has fold left basically all polynomial
type constructors are foldable and no others so it\textsf{'}s I prefer to think
of foldable as just a property of polynomial type constructors now
it\textsf{'}s interesting that we can define an instance of what Catalan recalls
in variant semigroup oh and what I just called in a previous code
snippet as if Abel pro factor neither of these names are particularly
nice as I said in variant just gives me all kinds of wrong associations
and semi Drupal is a difficult thing to do a difficult thing to understand
because it is not a semi group so semi group all suggests that it
is a semi group but it isn't so zip abou proof factor is the same
as invariant semi global I'm not sure what terminology is better neither
is standard neither terminologies widely used right so let\textsf{'}s look
at this obviously we have our in the contravariant position and also
we have our in a covariant position so again this is going to be a
pro functor not a functor no matter we can do a zip on it and I just
use my career Howard library to implement the IMAP and the product
methods now the product is the same as zip Justin cats library uses
the name product instead of zip IMAP is this Pro functor property
where you you can map fold 0 of Z a two fold 0 of Z B if you have
functions from A to B and from B to a so this is a typical thing that
the proof factor requires you cannot map a pro factor of a into profounder
of B unless you have functions that map in both directions because
you would use this function to substitute in the covariant positions
and you would use this function to substitute in the contravariant
positions and since you have both positions for your type parameter
you need both functions but luckily enough this type is sufficiently
straightforward so that my Harvard library can automatically implement
these methods and then I can implement zip as a syntax by just using
this product because zip is exactly the same type signature as this
product in the Katz library and now how will we use that so let\textsf{'}s
define some actual folding operations for numeric data for instance
the length of a list or sum of elements so the length is going to
be a fold with initial value 0 and updater that just adds 1 to the
accumulated value ignoring the value that is in the collection and
here i'm i've used the numeric typeclass which comes from the spirit
library let me see what was so ridiculous oh yeah here\textsf{'}s the spire
mass library so I'm using the spire math numeric because I found that
standard scholars numeric they are very hard to use inspire has a
good library it has lots of interesting types and I could recommend
using that so for numeric n we have operations such as plus minus
and divided and multiplying so on so for those it makes sense to do
a sum by folding with this update function that accumulates the Sun
starting from 0 now we can combine these two now these two must be
diffs rather than vowels because they have type constraints that cost
constraints so typeclass constraint is really a implicit argument
of a function so it must be a function is not not a value and it has
a type parameter so it cannot be a value anyway can be a valence color
it has a type parameter and/or it if it has an argument type typeclass
constraint but it doesn't really matter you can just do it like that
now if we apply the zip operation and we get a fold that accumulates
a pair of two numbers so the chemo is the length and the sum separately
so we can apply this fold to a list we get this pair and then we can
divide the sum by the length and get the average of the sequence so
in this way we already realize what we wanted we have combined folds
and this is a single traversal because this is a single at full left
operation now this is however inconvenient because we need to do this
combining and then we have a tuple and we have to take parts of this
tuple we would like to incorporate this final computation somehow
already into the fold so when we apply this then all of this is done
automatically and also we don't want to worry about this so much this
we want two things to be automatic how do we do that well so the idea
is that this final computation that takes the accumulated value does
something to it and gives you a different result perhaps of a different
type like here the type of the accumulated value was tuple and in
and the type of the result was just in we would like to put this final
computation also into the data structure that is the fold so that
when we apply the fold to a list all this is done automatically well
easy to do we define this fold one which is the same as before it
has the initial value it has an update here and then it has this final
transform which takes the accumulated value and returns some result
value and the types our za and our so we now we have three type travelers
in this data structure but so what we can have as many as we need
we find a syntax I do this fold l1 now unfortunately the syntax cannot
clash with other define syntax I need to do this full l1 I cannot
just do fold left I would clash with Scala standard from left and
in order to apply this a new comprehensive fold so to speak first
we need to apply it ordinary fold to the initial value and the updater
and the result of that needs to be transformed using the transform
so that is how we apply the phone there is still just one traversal
because there is just one call to actual fold this is the fold left
the foldable class has this hold help function so there\textsf{'}s only one
traversal and we'd like to keep it that way so there won't be any
even if we combine mini folds together it will just be one traversal
so how do we combine the fold while we do the zip and I just told
it to implement nice now the interesting thing that happened after
we added this transform a element to the case class is that now the
type parameter R is only in the covariant position so in the covariant
position the a of course it is a contravariant position here but R
is only in the covariant in the covariant position which means that
with respect to the parameter R this type constructor is a functor
so we use fixed values of other type parameters and only vary the
type parameter R with respect to that it is a functor so we just implement
automatically have a functor instance and now how did that happen
why is it a functor well strictly speaking formally speaking it\textsf{'}s
because the typewriter are only occurs in a covariant position here
but actually the implementation of map for this factor is very easy
you want to transform our to some T just modify this element compose
this function with the function from R to T and you get a function
from a to T and that\textsf{'}s it so basically the map operation is the same
as and then applied to the transform element of the tuple or part
of the case class so that\textsf{'}s why I did not write code here I just said
implement it works it is completely fixed by types now defining the
length and the some operations as folds now we have these type parameters
which I wrote down because you have to not on the right-hand side
but you need to write them on the left and so it\textsf{'}s a function definition
so now you see same thing except I put identity here because it\textsf{'}s
a transforms as identity I need to put it in let\textsf{'}s combine the sum
and the length like this we we do a sum zip line so that\textsf{'}s going to
be accumulator of this type and then we apply this function which
will divide the sum by the length and get the average so the test
works now actually this is still quite cumbersome to write this kind
of thing we would why can't we write just this we can we just define
syntax instead of writing this syntax that would allow us to write
that so here\textsf{'}s the syntax as an syntax extension we define all these
operations an arbitrary binary operation basically does this just
X\textsf{'}s if y exactly like what we did here and then a function and this
is the binary operation so in this way we can easily define all the
binary operations that we want and here\textsf{'}s the code now very easy to
write the double type parameters unfortunately are required or you
could put the type parameters here that would be less intuitive so
this is the way that we can combine folds in a single traversal note
that the same structure is required for scans of scan is like fold
except all the intermediate accumulated values are still kept in in
the sequence or in a container and so that\textsf{'}s how you would apply a
fold operation that we defined as a skin it is very easy because scan
left has exactly the same types of arguments and these two arguments
are what the fold structure gives and then you just need to map with
transform now unfortunately this is going to be twice the traversal
that we had because we do a scan left that\textsf{'}s going to create one sequence
and then we do a map is going to be a second traversal there might
be a way of avoiding it but that\textsf{'}s less important that\textsf{'}s certainly
just to traversals we can combine as many folds as we want in a complicated
way they're still going to be just two traversals so if we can somehow
refactor this to have just one traversal maybe by refactoring the
scan lift itself that would solve that problem that\textsf{'}s not the focus
of this tutorial so here\textsf{'}s an example so if we use the average and
do the scan instead of fold and you have all the intermediate averages
accumulated as you iterate over the list so finally I would like to
point out the difference between applicative and one addict factors
so we have seen that fold could be seen as a not function as a proof
factor and yet it has a zipper ball property and so you can merge
these folds into one now this merging is similar to component wise
information so for example average of sequins is a division of Sun
of a sequence and length with sequins and some and links are completely
independent of each other so that\textsf{'}s a component wise operation in
a sense and so that\textsf{'}s a click ative by our intuition now monadic operation
on the other hand would be such that we depend on the previous results
in order to compute the next iteration of the fold and so for example
we could compute a running average that depends on running average
that we just computed previously so we can combine folds together
but each new iteration would depend on the previous accumulated result
so that would be a monadic fold so let\textsf{'}s see how that works we are
going to continue to use this type constructor because it\textsf{'}s a functor
in harm and as we know a mu naught cannot be not a function could
not be contravariant or pro factor it must be a function so if we
want a monad so that there is a useful kind of flat map then {[}Music{]}
you need to use this we cannot use fold 0 that was not not fall to
fold 0 all right but actually it is more difficult than that because
when you combine two different folds the type of the value that you
accumulate must change it must be a tuple of values that you previously
accumulated let\textsf{'}s look at the type signature of the combined so you
see you combine I skipped over this but if you look carefully the
first fold takes values of type Z from your sequence accumulates values
of type a and returns results of Thailand a result of Type R the second
fold is a different accumulated type and so the final combined fold
needs to accumulate a pair of a B and it returns a pair of our team
and so this is not quite the same as the type signature of a usual
zip because not only this type parameter is modified but also this
one but this is necessary so it is a slight generalization of a zipper
ball or or zip or type type signature but this small generalization
is important and necessary and similarly for the flat map if we want
to define flat map it would have to change the type of the accumulated
value a so here\textsf{'}s what it would be if you want to do a flat map for
fold then it will take three it will take two two arguments one and
be some initial foldable then you take the result of that fold and
the function will compute some other fold using that result and then
you want some how to combine these two into a fold that returns T
but this fold certainly needs to accumulate a as well otherwise you
won't be able to get ours and are necessary for this one to work so
the resulting fold must accumulate here maybe there\textsf{'}s no way around
that so this is going to be again slightly generalized type signature
for flatmap where usually you would not see this these type constructors
would be absent and you would just have f of r r2 f of t returning
f of t but now you have to return this kind of thing and that is as
I just explained unavoidable so how do we do that well we basically
very carefully look at what is going to be computed when we apply
this combined fold so first of all what is going to be the initial
value of this type while the initial value needs to be of this type
or clearly we need to use the initial value of the first fold and
where will we get the initial value of the second type the only way
to get it if is when we apply F to something but to what we need some
R well the only way to get R is when you transform with the first
fold from some a and there\textsf{'}s only one a here which is this initial
value so f of this is the new fold that has initial value B so let\textsf{'}s
take that and put that into the tuple let\textsf{'}s now look at the update
how would they update work now the update needs to be of this type
clearly the only way for us to get a new value of a is to use the
update from the first fold so let\textsf{'}s call it new a now the only way
to get anything of type B is to go through this function f so we need
to apply F to something to what now clearly to some R and the only
way to get an R is to transform at the first fold and the only reasonably
correct thing to transform is in new a well could transform the old
a but then and this is not right because we want the second fall to
depend on the result computed by the first but this is debatable we
could have a situation when this could be a 1 here it just seems to
me that this is better to use an update in value and in a specific
application you want to see you this is so so this is a new fold so
so this is a new value of this type now what we need is a new B so
we need to update obviously this B we need to update with new fold
we get a new B so now this is the new alien new B that we accumulate
so that\textsf{'}s how the the updater works there\textsf{'}s just one place here where
we have some some some ambiguity some choice everything else is pretty
much fixed the new transform is going to be from a beta T and that\textsf{'}s
again pretty easy to understand that we have to get a new fold somehow
and the only way to get it to do this and then we transform with b1
and we get a tea and so let me return a fold that has this in it this
update and this transform so let\textsf{'}s see how this fold works let\textsf{'}s have
the running average of the running average so one way of doing this
would be to do double traversal which is actually quadruple traversal
since each scan is the two traversals but let\textsf{'}s ignore this for now
so it\textsf{'}s a double traversal so first average gives you this and then
when you again do running average of this another scan with the same
fold then you get this now let\textsf{'}s combine the two averages together
in the melodic way so how would that work we do the average one do
a flat map so X is this running average after transformation so it\textsf{'}s
a running average and for each running average return a fold that
accumulates that running average does not actually accumulate values
of Z from the initial sequence it accumulates this running average
for each fold and then we divide that by length so see this is how
we would write that and now a single scan gives us exactly the same
results so in this way we have combined two folds into one in a monadic
way we can use the for yield syntax the functor block which is easier
to read and that would look like this so X is the running average
from that accumulator is the result of this accumulation which depends
on X which accumulates the values of exit actually ignores the Z it
accumulates the values of X n is the running average or running value
of this fold so these variables are to be visualized as running values
of the fold and finally we divide this accumulator by very visual
and we have again the same result so I would like to emphasize the
difference between negative fold combination and magnetic fold combination
is that applicative folds cannot depend on each other\textsf{'}s intermediate
results but monadic fold combinations can that is the main intuition
behind understanding the difference between monads and applicative
factors the packet of factors Express computations that are independent
of each other there are kind of component wise computations but monadic
combinations describe computations that are possibly dependent on
each other\textsf{'}s running values so the previous value can influence what
you get in the next map now there is a library called origami that
gives you a monadic fold but they are actually not magnetic they're
moon advanced if you take a look at that you would see it says monadic
fold but actually they are not the same as what I just described they
must operate on a monad and their update has this type which means
that your updater includes a monad as a as a result and every iteration
of your fold must flatmap over this monad so that\textsf{'}s why I would call
this a mu not valued fold so the result of the fold is a monad value
and so every time you accumulate your result you updated you actually
have to evaluate a flat map on that moment so that\textsf{'}s a very different
thing which is useful in different ways it is not the same as the
Magnetic composition of food so take a look at these libraries in
more detail if you're interested and the final worked example that
I'd like to explain is the difference between applicative parsers
and one addict parsers so again this is really a difference between
how we compose these parsers together just like with folds how you
compose phones together you can compose them in a negative way so
when they don't depend on each other but you must compose them in
a melodic way when they do so the same thing happens with parsers
as I will show now parsing is a very big topic with a lot of different
algorithms and complicated grammars that you can parse in different
ways and I'm going to explain very basic things that you can do easily
while trying to do this on your own you will certainly run into trouble
but that\textsf{'}s because parsing is hard easy languages can be parsed easily
so that\textsf{'}s why I take examples of very easy languages for parsing so
my first language for parsing looks like this it\textsf{'}s either a number
so this is end of file or end of string either either a number or
it\textsf{'}s this HTML tag that I invented with a number inside and a closed
tag or or it\textsf{'}s several of these tags and there\textsf{'}s always one number
inside and the tags must be balanced there must be only one number
and the idea is that you take a square root as many times as you put
these tags so you evaluate this to a number by taking square root
as many times out of this number as you have the tags opened and the
tags must be balanced so here\textsf{'}s an error for example not closed not
opened open closed but then there\textsf{'}s junk at the end which is also
not allowed so those must be errors those must be signaled as errors
so here I just created a type for errors which is just a list of strings
and these are the typical errors that I wanted to detect tags are
closed now I'm not closed not or not opened or there\textsf{'}s no number and
so on so how do I even approach this situation well it\textsf{'}s a very simple
idea is that a parser is a function that takes a string and it tries
to get something out of that string and if it succeeds it gives you
a value that it computes and it also returns the rest of the string
that did not consume so it consumes some part of it and returns the
rest of the string here\textsf{'}s a type that could be used for very simple
situations like this where you take a string and you return a tuple
which is either of error and some result type and also unconsumed
remain remaining portion of the string now if you failed to parse
then you return error of some kind and if you did not fail to first
on your return the value that you found computed in some way and so
this is the first idea is that you will define the values of this
type and you will combine them and the language parser will be a combination
of these smaller simpler parsers so here are the simpler parsers that
I found necessary for this language the first the simplest parser
is that it\textsf{'}s the end of file so the sparser succeeds only when the
string is empty now that returns unit so it\textsf{'}s a parser with unit type
parameter it returns unit otherwise it returns on here so I'm going
to use that when I require that there should be nothing else anymore
in the string and the second parser I found you the necessary is the
one that actually gives an error if there is no content in the string
so it kind of says there must be content in the string otherwise it\textsf{'}s
not right then I have a parser for a number so I have a regular expression
I'm just using very basic tools it\textsf{'}s certainly not the best way to
parse a large amount of data quickly but I'm interested in the principles
of how this works soap our servant will take a string it will match
the regular expression on the string so I'm using Scala regular expression
standard library which operates on string as as if it\textsf{'}s a case match
and each variable here the pattern variable will be equal to the group
that is matched so after this if this is matched and I have this number
and I have the rest of the string and I return this integer and the
rest of the string and if I did not match then I say there\textsf{'}s no number
and I return the entire string I didn't consume anything so in the
same way I define other persons so for example open tag if it\textsf{'}s this
then I return that otherwise I'll return errors close tag all right
so these are my test strings now how do I combine parsers this is
the most important question so the first Combinator is the zip like
Combinator\textsf{'}s applicative come to enter so let\textsf{'}s call it like that
and the idea is that I will combine two parsers let\textsf{'}s say parser a
and parser B may combine them by letting first parser a parse something
then also letting parser be parsed remainder and then I gather their
errors together in an applicative fashion so if they gave a result
great I'll return a tuple if they gave errors and I collect all these
errors and if there are two errors from both of them then I collect
all the errors just like we did initially in the example with either
where we could define the applicative instance or map to by collecting
errors rather than stopping at the first error so that\textsf{'}s the implicative
Combinator or zip of the two processors however note that the second
parser depends on the first because the second parser runs on the
rest that is remaining after the first parser has run so there is
a dependence of the second parser on the first just that this dependence
is not in the type a it it depends on the other things on the context
and the string that is passed around invisibly invisibly that is to
the types a and B the type a doesn't know that there is a string being
passed around so from the point of view of types a and B these are
independent but actually they are not independent so the parser B
is run after parser a has has run however it is applicative nevertheless
because parser a failing does not make parser be necessarily fail
parser B could succeed when parser a fails and then WordPress really
could also fail and then both errors would be collected so that\textsf{'}s
the difference there\textsf{'}s also a monadic like Combinator that uses flat
map where we first do parser a when we discard its result and then
we do parser B so if the parser a fails then nothing will be done
so this will not collect errors from person B another important Combinator
that has nothing to do with monads or applicatives is this alternative
come to meter which is that parser a will be run and if it succeeds
parser B will be round but if bursary does not succeed sorry if if
parser a fails parser B will be run if parser a succeeds parser B
will not be run and so parser B is actually here passed by lazy evaluation
for reasons that I will explain shortly so how do we do that so first
we run parser a we get the result and the rest of the string if the
result is not empty then we just return that if it is an error well
that error is ignored and we try parser B so that\textsf{'}s the alternative
and when we define map and flatmap because parsers are functors let\textsf{'}s
check that is a factor there\textsf{'}s a parser type parser type is type parameter
a is here to the right of the function error so yes it is a factor
now let\textsf{'}s define the language the language is defined like this so
first of all it must be not empty so and this is the melodic Combinator
so everything will fail if this fails so if the string is empty then
everything fails right away nothing else is tried if it\textsf{'}s not empty
and we try to parse the number if so we mount it to double if it fails
then we try open tag and then again we use a monadic Combinator because
if that fails that we should fail that\textsf{'}s either a number or an open
tag and it should not even try every anything else so it what happens
later is again we use language your exits a recursive call open tag
can contain any other thing in the language it can again contain openText
so we do a recursive call and then close that now this is an applicative
Combinator so if this fails we can still check that this fails or
not and the result is then mapped into a square root because we have
here if this succeeded then we had a tag which is a square root tag
so we have to compute a square root so in this way we define just
the language of these tags and then the final parser is this recursive
language parts are followed by end-of-file and this is again an applicative
combination so we can detect junk even if this failed junk at the
end of file will be detected and then we map to the first value returned
by this so then it\textsf{'}s a parser of double finally we define the function
parse language it takes a string and runs this language parser on
the string and takes its value which is going to be either of error
or double and here are the tests it works for example parse language
of this is 123 first language of this is 11 square root of this first
language of that is 10 this is square root of square root these are
not closed so in their junk at end and here we actually find several
errors there\textsf{'}s not opened not closed and here is not opened not closed
so this for example we find that the tag is not open the tag is not
closed and there is a junk at the end so obviously we are able to
find all those errors at once so as a second example of a language
consider this a number surrounded by tags but now the tags are arbitrary
their tag names are arbitrary they just have to be balanced so there
it must be B and B C and C now this is a different language where
the parser depends on the result of the previous parse now here the
first row did not depend on the result because this is parsed independently
of whether it is inside a spirit or not this by itself is parsed and
gives you hundred regardless of where it is it does not depend on
that but in the second language that I consider that is not true because
this needs to be followed by C which so if they said if this were
C that\textsf{'}s an error so you need to know that you have first be here
in order to parse this correctly so parsing this depends depends on
parsing this and that\textsf{'}s why we need to use a monadic Combinator so
I again define a few different small parsers and combine them into
larger parser so I find two parsers that parse any tag and return
the tag name as the result and then a parser that takes a specified
tag that should be closed as an argument so now this is a function
that returns a parser and I'm going to use a flat map so that it is
very similar parsers before I have an end the file is error than I
person number and then if not a number then it\textsf{'}s any tag but the tag
that I parts it needs to be closed right here so in this way I depend
on the results of the previous bars so this is when an addict combination
is is required and here are the tests and just to highlight the difference
so we do find several errors here as well because we use applicative
Combinator here and here as well but now we find fewer errors at once
because for example here remember this incorrect input that was tested
here here we got that it is not opened not closed and junkit and here
we only see that it\textsf{'}s not opened and jumpa then we do not see that
this is not closed because the closing tag unethically depends on
the result of the opening tag which failed and so nothing was tried
so that the parser a little parser that was here never got called
and so it never had a chance to fail and to tell us that the tag was
not closed so unfortunately there is no other way to parse this language
in this in this simple minded approach because we have to use this
flat map we have to depend on the result of this in order to check
that this has the same name so this is a difference between magnetic
and duplicative functors applicative factors describe computations
that so to speak they they occur component by component independently
so there are several parts and each part is processed independently
and the results are all accumulated so map to visa is a good example
so you have several parts that are all processed independently component
by component and the results are put into another container or as
monadic combination means that each next step here depends on the
result of the previous step and that is sometimes necessary however
the parsers is an interesting example because actually as I just showed
parsers do depend on previous results because the parser that is next
gets the remaining string and so it depends on how much of the previous
how much of the input string was consumed by the previous parsers
and so for this reason even if we only have applicative parser Combinator\textsf{'}s
you still cannot say they are fully independent and so for instance
you wouldn't be able to parallelize the person but in many cases applicative
combinations can be parallelized as we showed in the example with
the futures so here are some exercises on this material so here you
should implement map to or IMAP to is appropriate for these type constructors
some of them are not funky and as I showed for the semigroup but you
should do the same for the Montoya to you find a typeclass instance
for the pair then you should define a monoid instance for the type
FS now this is s is another type parameter is a fixed mono ed type
and so it\textsf{'}s just applying a type constructor to a fixed type should
show that this is a monoid this was similar to what was done in the
previous chapter for monads but now for applicative so sure you don't
need F to be a moon and for this and some exercises for parser and
folding Combinator\textsf{'}s this concludes part 1 

all right so this is about goals and the main question has well I
will talk about rules and output about parsers platform is so how
would we compute standard deviation of this list of data well we can
compute it in simple way and beautiful ends so this is always the
length of this list don't give the average refused average of squares
and you standard deviation well this is a simple way of doing it three
men were statistic widths it to give the way of doing this which is
to introduce the creation factor which is n divided by n minus one
due to sample variance all right this is it now the problem with this
competition is that which reverse is list three times every time you
do a length sum or the map traverse this list so actually here matures
it four times because map traverses and then assembles of traverses
so the way to avoid traversing many times is to further wait these
operations as some kind of full bridges and so let\textsf{'}s look at the type
signature of fold Oh blood for example what is the type signature
of net it takes a value B IV and it takes a function that updates
the accumulated value and so it goes over your list starting with
the initial value v the initial value of the accumulator and then
for each value age from the list it holds this function to update
the accumulated value and finally you have the accumulated value that
you output so that\textsf{'}s the type signature of fold so you can do this
with a fold start with for example the computer sound sort of doing
data to the sum you say you fold left so but the Sun let\textsf{'}s put this
into your blog okay so how do we compute them in for example you fold
with initial value 0 and the function that takes helpfully tells me
what it takes so accumulator and bullets would X going to well I'm
going to add 1 to B that went to be the length so I can I can express
those things very easily some is this sum squared is this right RZ
inz right now however we still if we combine those were still ready
to have multiple universes so they are yet but we want to pursue is
that we want to have some way of combining these folds automatically
and the single universal so that we don't have to revolve include
of course just do more work and make a single fold which will do all
of this will accumulate a complicated round will have to collect a
lot of data you cannot just do it in simple traversal like this have
to accumulate the length separately we have to accumulate the sum
separately we have to avoid the average squares sum of squares separately
and the end we'll have to perform this computation so that\textsf{'}s kind
of difficult we'll have to accumulate a triple at least and then at
the end we'll have to do this so we could do that by him but instead
we want to write some code that will automatically combine folds like
these I wanted basically you'd be able to combine these things together
automatic so that it automatically decides what needs to be accumulated
and we don't want to see all of this so the first attempt to do that
would be just very straightforward so let\textsf{'}s look at what we want to
combine so we want to combine bowls so once at forward but one of
them that we render them by the idea is that this data data that you
have to pass before life that is what you want to come you want to
encapsulate this data in a new data type and combine those somehow
and then at the end he will pass the combined data to the faultless
be wonderful left in the end and that\textsf{'}s how we will accomplish we
want combined the day time that both left that\textsf{'}s the idea what is
the data that the form of days the data consists of two pieces or
two parts the first part is a value of type B the second part is dysfunctional
others therefore define a type it has these two values and call it
foap 0 it has a type parameter B and so it has initial value IV and
update function of type the easy one is who I call it Z just so I
need to type parameters actually right so this is the signature of
boatlift f of E and I have some type of their sequence element both
of them need to be type parameters now because I'm trying to generalize
it alright let\textsf{'}s let\textsf{'}s call this a instantly white hole it'll be okay
so this is the data that fold needs to perform its operation now we
can define a syntax to apply our to apply the full duration today
and so we want to want to be able to define values of this type and
fold with them and then we also want to combine them so let\textsf{'}s do one
first first our syntax to perform old love using and that\textsf{'}s obviously
going to be a sin tax extension right it\textsf{'}s going to be implicit class
hold you syntax some type parameter which is going to take a sequence
of a let\textsf{'}s say right let\textsf{'}s that\textsf{'}s miss good for a listing same time
take a list of a and define a function which is going to be all 0
only taking actually messy here take an age old hold 0 of Z of a Z
and the result is going to be a B right so that\textsf{'}s going to be s hold
left of fall 0 needs all all 0 and a done so now we have this syntax
and now let\textsf{'}s define these parents for example playing plan 0 links
in some type actually with but what type would be we fold 0 of some
Z and say double that\textsf{'}s not not very generic now that do need is the
odds be too generic it can be done with the generic and now length
of its list or double right it\textsf{'}s going to be 4 0 of 0 and simulator
bar or interview waiting plus one right so that\textsf{'}s how you find a phone
now we can apply data don't hold 0 of things that\textsf{'}s should be all
the thin I'm going to run this right now for the main errors okay
Sergei what you've done is are you taking this whole operation when
you were originally running as you look at the other nine you stored
that operation itself with case class they executed bigger right so
I started a time that the full apparition needs and my idea is that
I want to be able to combine that big so that they their presents
the folder hasn't yet been done right it\textsf{'}s waiting to be applied and
here\textsf{'}s I still want around this test ok right so so this is how I
will later apply these fools now for mine so what does it mean to
combine I want to have a full 0 of za I don't have a full zero of
B I want to get full 0 see what of a big maybe pair baby right so
if I can do this then I can combine arbitrary folds into a big one
automatically but I can just apply that that would be a single traversal
so let\textsf{'}s see how we can do this so they come that combine function
has a type signature that\textsf{'}s very similar to see lists so I call it
let me call it zip zip zero I have folds your outer for one later
I'm permits I hopefully everybody will show that because that\textsf{'}s also
quite interesting so what is M 0 0 is going to take folds here on
the a40 of CV but to give me from 0 of saying I need a parameters
C B right how do you combine that kind of thing well let\textsf{'}s look at
the type Oh so we haven't - for basically we have a slot for this
basically named to having two parts listen this so we have this for
a and we have this for me we have a we have this function and this
function for me right we need a B and if we seem to be right so we
just want to return new in it and new update and so this is going
to be new in it type a B and you update of this type and if we can
do this we're done we have combined how to combine this well obviously
so much we can do to combine this a and this B alright so that\textsf{'}s all
0 in it or 1 right Elsie\textsf{'}s latest is done now how do we do this well
each return a function that takes this and returns that bullets start
writing the function is see check the types now we need to return
a tuple of Av by using those we can get an aid we get an if you have
an N Z plus F 0 of AZ every one of these sorry F 1 of easy right what
is oh oh yeah f 0 update ok so in this way we have returned the correct
ID and we have used F 0 and F 1 somehow by combining them which makes
sense now is that really what we want well yes because how would this
updater work it will take the previous pair of a B it will update
the first one using the first operator and now then the second one
using the second nominator and it reuses the same C which makes sense
is the same sequence verb folding over so this code in cups awaits
the idea that we're folding two things at once but doing only one
traversal but let\textsf{'}s now define another fold so we define length so
far let\textsf{'}s define some H we know how to do let\textsf{'}s define some squared
which is going to be like this let\textsf{'}s use this zip zero to combine
what will happen some and length which is going to be super serum
of some zero length here and look at the type the type is correct
now it\textsf{'}s going to fold and produce a repair Dallas apply using zip
all right so I'm going to apply holes you on this sum and length and
that\textsf{'}s going to give me a tuple write us all is something length zero
and then I say sum divided by length five point five because that\textsf{'}s
the average of this yes okay so this is how we succeeded already we've
already combined two folds and there\textsf{'}s only one chairs of course this
is very ugly have to do all this and this two plane and all this stuff
and then we have still two separate calculation after this is inconvenient
but we would like the code to be something like this you know data
does fold and then some divided my ladies wouldn't that be nice we
could have code like this and then we could have here a larger computation
some example you know some squared minus some time some something
like this no why can't we do it like this we'll be great we'll be
very declarative you can't do it so the way to do it is to understand
first what he want this once you understand what she wants design
your declarative language then it\textsf{'}s always what you need to do we
already know how to combine both so all these need to be false you
just need to define the creations that combine them and at the same
time perform the final computation after the forward so far our folds
always will give you some tools he wants to combine the tuples in
the final computation into single value once we realize that we want
this the natural thing to do is to put that final computation into
the full data structure let\textsf{'}s define fold one so I'm going to define
fold one by adding final computation of type a to me let\textsf{'}s call it
hard to be more visual so a is accumulating our is result so we're
going to have a structure fold one that encapsulate s-{}- both the
folding and the final computation after falling so now if we combine
these folds then this a could be a complicated tuple type but this
result computation will perform all this extraction out of the two
whole automatically and here\textsf{'}s single value that you want so in this
case we will be able to implement things like this and that what will
be remaining is just indexed we find syntax for this which is reasonably
easy so this is the main idea of how to combine false good thing else
is now just implementation we need to define again sin tax reform
for left we need to define the same things define the zip and need
to esta let\textsf{'}s work let\textsf{'}s just that anything so for one syntax or have
an old one right now old one still does the same things as anything
has updated but then has an extra type track which is going to be
any part right for the result and the result is going to be its own
either side round here and the result is going to be old one the result
of this and the this is of type our okay so everything else follows
pretty much so double-double int chickens well actually I can do this
or I can just say it\textsf{'}s an instant I accumulate and then I have okay
so let\textsf{'}s check that this works actually the things won't compile them
know yet but right now onion is except one which under to define and
okay so let\textsf{'}s do what\textsf{'}s story I remarkable I held upon a needs if
one here he\textsf{'}s someone length warm and is it ones to be old he paid
are one let\textsf{'}s call it a 1 R 1 with a two or two it\textsf{'}s going to be a
1 into R 1 R 2 now the zip still needs to needs to do this needs to
take a to talk and automatically create for me the accumulated type
which is going to be a two-fold will not use to kill plate and the
result type which is good to use it to turn right now let\textsf{'}s implement
the zip it\textsf{'}s a little more complicated it\textsf{'}s basically the same code
as we have the previous tip except we're going to have a transform
a deal right so it\textsf{'}s exactly the same game same code will work except
I need to do a new result and so new result of Type R 1 or 2 is going
to be an f0 result sorry what doesn't he result not the right type
and it\textsf{'}s going to be in one it\textsf{'}s you going to our 140 so it\textsf{'}s going
to be kiss anyone to going to have zero result one diamond one is
not to that you remain right done now just for your reference all
of this I have I have implemented all of this automatically another
another file which I'm not showing I have implemented this is zip
function on Z automatically using a quick outline room keys of marinus
basically implements functions based on type signature and the type
signature of this function is sufficiently respective so that only
wild reasonable implementation can implement is this Margaret I have
very Howard library anyway let me just show you where this this one
so I could just implement it it implemented hold this automatically
this code is in some sense were late it\textsf{'}s boilerplate in the sense
that the types we paid what I have to do there\textsf{'}s not much choice alright
let\textsf{'}s check that this works I'm just going to do some some squares
I need to have more type parameters here or one need add identity
are not transformational one all right done of one some live one and
see this works due to the test name this man in yes alright so it
works but now we can do much better we can actually define average
is it for I'm going to skip the types actually these types are not
necessary if I do a sip one of someone length one and then I what
I want is I want to add a transformation to this alright so how do
I add a transformation now I I can the type of this is this so I could
have a transformation I will take this result and divide it made the
final result let\textsf{'}s have a function of as a transformation so let\textsf{'}s
do syntax extension we have a full one syntax yes where they have
one x what doesn't matter what that means okay so I take a fold old
one so I need these type parameters and I returns something that has
a committed which is going to be and then some function are going
to see is name for one see 80 which is going to be full one don't
open result falls for one result and then okay so that\textsf{'}s going to
be my crew so I'm just I'm going to keep the fold as it is except
I'm going to change its result by a new function f so now I can do
and then some length points with some dividers what is wrong ooh a
hole in it oh because I already defined some but there\textsf{'}s a type of
this this is a two-fold why is that a tooth oh oh yeah because it\textsf{'}s
I can't I have to do in case that\textsf{'}s right okay it\textsf{'}s done so now I
can do this I can just compute this image it is still a bit verbose
right if you have to do all this stuff so in order to make it less
if it was is what you can do let me just show you the code on the
length of time here\textsf{'}s what I don't do I can I can do it there is magic
extension on the phone it\textsf{'}s exactly the same hole except now it\textsf{'}s
permit rise on numeric result and if the result is numeric I can do
arithmetic I can do plus minus and the result is that I can have I
don't have food like this where I directly fold all the one using
this as my and the Nationals and the result is so the syntax is now
almost like we wanted except I have to put the double in here because
in this code it\textsf{'}s completely genetic it\textsf{'}s a generic over numeric numeric
item in whereas in my example quote here I have double everywhere
explicitly so I don't need any type parameters but if you want to
have your code generic then that\textsf{'}s what you need you define your syntax
which is so all this code is going to be in the library easily and
your your user calls upon me like this so this is how you combine
folds into well you can also do you can also use can left with the
same data because scan is like a fold except you keep all the intermediate
accumulated values and so you can you can do scan left or the fold
data and in this way you can just use these fold things as the control
your scam in traditions in so for example you can do an running average
running average is this so I'm just doing a scan with this average
one with a defined can I get this so now if I combine several folds
into one I have put them into the argument of this scan one and there
will be one traversable technically speaking there to traversals with
mmm but I think it really and it there\textsf{'}s only one logically speaking
there\textsf{'}s only one fold with your appliance folders come together and
it encompasses the entire computation so I could express all kinds
of things like standard deviation like that I can also define pure
for fall so for example if you look at my plan here not sure if I
don't have time to go to do this this computation has Falls but I
might need to have constants as well for example a standard deviation
here requires this constant one so I might need to have a constant
as full fold that always returns one so I can define that but me we
do that here in a chamber or one so I headed a transformation defined
and constant old so this is what we call this pure one it\textsf{'}s going
to be some X and it\textsf{'}s going to give old one are see our heart so this
fold one is going to be starting from X 1 to have function that just
gives me X and it\textsf{'}s going to have a function that returns an X whatever
it\textsf{'}s it\textsf{'}s whatever I want I just want to return X I don't care about
any of a connection so if I have a phone like this then I can say
for example here of one or pure of two and I won't have a full that
always returns that constant and I can combine that with other fools
way that I combine for it is in the zero and so then I could amend
the computations isn't one let me show you okay any questions at this
point so we have basically achieved this syntax yeah basically achieved
our goal we can compute like this but I would like to show you now
is that actually this fold is a moment in lavender arm and so you
can implement in in a sense it\textsf{'}s frankly speaking it\textsf{'}s kind of a more
not I you can implement flat map and the only problem with flat mount
is that flat map could change the type both there\textsf{'}s some other folks
and so the accumulator type needs to change now you might have to
accumulate more than one value so a flat map they can in the usual
way does not allow you to change other type parameters it changes
one type parameter but not others it would have a flat map in the
usual way to take a full of art and function from R to full of T and
you're returning full of T however it won't work because you need
to accumulate more Nathan so you're forced to have a different type
parameter and there\textsf{'}s an inner zone so this is not really implement
in a sense and it is a generalized kind of that but the flat map is
a flat map so it\textsf{'}s usable in exactly the same way so after I implemented
this loudmouth which again it\textsf{'}s implemented kind of automatically
just try to try to see what what needs to be done and now first hit
accumulate the first fold and then you transform that when you take
the army apply to function you take the second fold accumulate that
is it\textsf{'}s kind of automatic so the result of this of assure you this
code very interesting-looking I can now write fold combining code
in this syntax now these are different combinators them zip because
they can depend on each other so first I take the average X is the
running average and then I can define a full that uses that X to accumulate
that running average in another accumulated and then I also have the
length which is a previous fall and then I divide this by them so
this gives me a running average over a running average I have a first
Pole and the second fall depends on the first event on the results
from the first I remind you that average or way to compute the result
divides already sung by the ladies this is already complicated for
I'm combining it with other tools so using this syntax it\textsf{'}s much more
visual what I do the result is a fold and if I apply this fold to
a list I get this which is you see it\textsf{'}s growing much slower because
it\textsf{'}s a running average of the running average so in this way I have
combined folds phonetically which means the second fold depends on
the results from the person using zip I combine forms in a way that
don't that they don't depend on each other they all running in parallel
from my signal when I combine them using flat map I can't make them
run so to speak sequentially later for and now this can be an arbitrary
updater but it depends upon the results of the previous fold an arbitrary
way this is this X is not the accumulated value inside this form is
the result is a running result after transformation it\textsf{'}s very powerful
way of combining computations and the result of this is still just
full it\textsf{'}s not yet running it\textsf{'}s just a fall I don't care about its
type here it\textsf{'}s different from zip so saving is duplicative convolution
and for a flat map is the melodic information so this illustrates
the difference between applicative and all not a complicated combination
means that the structure of the computation doesn't depend on previous
results and phonetic combination could depend and this could be a
different form each time depending on this X so that\textsf{'}s a much more
powerful way but yet and yet I have a single traversal so you see
this food inside it there is just a single big updater of motion that
is going to be substituted into the scan left it\textsf{'}s going to be just
a single Traverse with that the beta version and all of that is automatic
all right now I'd like to leave time for questions anything here needs
to be clarified let\textsf{'}s see the code for a cold one again yes for one
is this so it is a initial value of the accumulator it\textsf{'}s the updater
function and the final transform from a college transfer from a to
R so if you look at this pipe constructing the type parameter R is
in a covariant position but the type parameter a is not so it\textsf{'}s not
that functor if you spective are so sorry with respective a so it
isn't funky with respect to R so we could make it it will not only
with respect to honor so unless we add the transform here we could
lose him like we did with full zero not possibly do flatmap is a the
typewriter a occurs in a contravariant position here and the coherent
position here so zip can be implemented nevertheless zip does not
require being so it can be implemented many places but so see I'm
using automatic implementation for words all that I'm using also this
syntax or factor instance this is not not very important for this
you like if you want to know about this asking basically this has
a functor instances of one of instance but only the monarch with this
I change so the time traveller in the middle used to change otherwise
this given to us by Allah so there are libraries but implement these
foods to rest on unfortunately none of them were published in a at
the same time they're very small there\textsf{'}s not much code rather more
more than I showed here but much much more than this there are some
convenience is there are some predefined falls from the Marek data
basically it\textsf{'}s not a lot more functionality on this there are maybe
some more conveniences there are some libraries in differences I don't
think it is in the standard of living of any kind yet not sure something
in it so there are libraries I would say well maybe there aren't so
many use cases where you want to combine these fold but I think it\textsf{'}s
instructive to look at this to get an idea what you can do the basic
idea here is that we wanted to combine communications wanted to do
that you first define a data type that represents your computation
but does not get performance so your computation is fully defined
and specified but not yet performed when you define combinators from
that so you can combine your computation you can combine them as negatives
whereas once you have a pure flatmap have map yep zip so you can combine
your computations the variety of ways and then at the empty run once
you have combined all this your code is done at the end you run the
computation so you can organize your program as these computations
that are really data structures that are combined in flexible ways
but you run it at the end so that\textsf{'}s that\textsf{'}s the main idea and that\textsf{'}s
what enables is a musician all right anybody if remote having a question
alright so that was mine folks I didn't get to talk about our things
but that\textsf{'}s that\textsf{'}s quite seen in in spirit you present Mercer as a
data structure and combine them and you run my question is how you
combine them and the order to use and that you look for civility of
zipping them together or flat map and you know it you know how to
do with those once you find those we thought we have a pure and they
were flat nothing in the map I was here and once again we find that
which is combined in a very flexible way combine all of the divisions
we have a commune specific language of sorts and then you run it all
right well we're out of time thank you very much 
\end{comment}


\section{Laws and structure}

\begin{comment}
this is part 2 of chapter 8 continuing applicative functors and pro
functors in part 1 we looked at practical examples of applicative
factors and pro founders and their use in part 2 we concentrate on
the theoretical properties of these factors to begin recall that applicative
factors have the map to operation but also they have map 3 not 4 and
so on do we need to define them separately for all n map in which
would be unfeasible perhaps or can we have it in some other way and
the answer to that question leads us to an operation called app before
we look at the properties of this operation let\textsf{'}s try to define map
in on a specific function either of string a so consider this type
constructor which is a factor in a and let\textsf{'}s try to define map in
and use it let\textsf{'}s see if we can do something better than just doing
up in here is map 2 it takes top of a up of B it also takes a function
from a B to some Z so a B and Z or arbitrary types parametrized here
and we return up of Z so how do we do that well for an either that\textsf{'}s
straightforward computation we match if there are two left we use
the monoi against a some string we were just concatenate the two strings
and otherwise if one of them is left one is right then the left remains
because that\textsf{'}s an error of some kind so we propagate the error and
only if we have both in the right and then we can apply the function
if so then we return the right of f of X 1 X 2 so it\textsf{'}s obvious how
to generalize this function to n arguments instead of 2 but the code
would have been very complicated to write and we'd have a lot of cases
so one solution would be to use a list of arguments and record over
it in some way and the second solution is to use curried arguments
which is going to lead us to the app method so let\textsf{'}s look at the first
solution so this map in one takes a list of up aim and returns an
OP of list a because can't without we don't have a function that\textsf{'}s
just instead of a function of n arguments let\textsf{'}s just put all these
arguments into a list so that will be sufficient we can always add
a function after that so we can see how that works if there\textsf{'}s an empty
list we go into an empty list and for a list having a head and tail
we do map to his head and then the rest we use map and one recursively
and the function that maps to uses is just appending X which is the
head to the list T which is in the tail after we already did my own
one so we have an optimist a so T is placed and X is an a so that\textsf{'}s
working but it\textsf{'}s not very great it\textsf{'}s still quite clunky to use because
then we would have to have a function that takes a list of arguments
so using this in practice would be quite inconvenient so let\textsf{'}s try
to see how we can do it better and the starting point is to define
a current version of map to lab two takes two arguments like this
and the function f takes two arguments like this now if we instead
use the curried version then a function f would have a type signature
like this so we would instead of taking a tuple of KB we will take
a and return the function that takes B and returns Z so that\textsf{'}s equivalent
but it allows us to do an interesting thing namely we have now a function
from A to B to Z and instead of taking a pair of a B and returning
of Z we also carry that so we take up a and return a function that
takes open B and return of C so that\textsf{'}s clearly just a rewriting of
map to using a different APA a different type which is equivalent
to the previous type so there is nothing new really except for this
current and a function type instead of unhurried now f map does not
have this type signature but here\textsf{'}s the definition now let\textsf{'}s also
introduce this syntax which will be more convenient remember we in
the short notation we often use this kind of notation when a function
is f mapped over a container so then we can just define that with
this index it\textsf{'}s just to write this instead of that so now once we
do that let\textsf{'}s apply F map to F of this type so why does F may not
give us this why do we need F map to that\textsf{'}s the question well F map
doesn't map this to this what does it do f map would take this which
is of the form a to something and after F mapping we would have op
of a to op of that something so the type will be like this OP of a
going to op of B to Z and that\textsf{'}s not what we wanted to have over here
we wanted above a going to op of be going to off of the so that\textsf{'}s
why F map doesn't work this way and we need F map - so what is missing
forgive me to be able to work this way so what is missing in a map
that F map - does here well clearly what is missing is to be able
to transform this into this so this is the transformation that f map
doesn't have but I've mapped two hands somehow AK map - already does
this let\textsf{'}s denote this transformation by app so this is how we usually
define F so this is the transformation that if added to F map will
give us F map - well we can define this transformation for either
just in the same way most more or less it\textsf{'}s a slightly less code to
write but basically the same code just there there\textsf{'}s one fewer argument
because the function f isn't here see the function if would be in
the F map so by considering app we have simplified our life F map
to has two concerns it takes this F it needs to map it to be and also
sorry I'm looking at that map I've map - it has two concerns it needs
to do this thing with two arguments and also it needs to apply F whereas
map only has one concern it only disentangled the two arguments somehow
and f is handled by map so let\textsf{'}s define F map - through app and F
map to see how works now for convenience that\textsf{'}s defined in fix syntax
for help which will be this it\textsf{'}s just so that we can write we can
write fa b star fa instead of up if i be okay so that\textsf{'}s just syntax
it doesn't change what this function does now with the syntax which
is defined here we can now define f map to via app and death map so
how do we do that well we need to return this function so we take
open up any take open B we need to return an OP see so let\textsf{'}s first
apply F map to up a so f has this type signature applying F map of
F to pop a gives us up of B to Z because F maps a to a function of
time bitters so now suppose we have this X so we could define it like
this now we can use app on that X and transform that X into this so
app of X of app V would be of type opposite so this will be out of
this of OB now that\textsf{'}s kind of clunky but if we write it in this in
fix syntax we write this instead of that and we write this instead
of that so in the Scala syntax these two operators will associate
to the left because the only way to associate to the right is to use
that colon as the first character of the special syntax of the of
the operator so therefore we can simply write this instead of F map
of f of opa of app and so on so the syntax is that first we compute
this so it\textsf{'}s associates to the left so it\textsf{'}s as if we had parentheses
around this around F F map OPA app OPB so and this syntax is very
similar to just as if we had have been able to directly apply a function
f notice this function has this type as if we could apply it directly
to OPA and OPB although we can't because F needs an argument of type
a and this is an Okie of it so it\textsf{'}s a functor of a so we can't directly
apply F to OPA this would be incorrect in terms of types so with these
special separators we can do it now so here\textsf{'}s how we can define F
map 3 OPA will be be obviously going to this what\textsf{'}s the final map
for like this so you see with this weird-lookin syntax we can define
f map 3 of map 4 and so on in a very easy way and we can actually
use that directly we don't need to define f map for and call it because
this code is so concise already so let\textsf{'}s see how we can just use directly
these operations now I just remind you that these operations are f
map and app they're just written in an infix syntax there is nothing
new about them or just F map and app so having these operations let\textsf{'}s
have a little test and do the safe divide so we divide by a number
but if that number is 0 we give an error message so if if it\textsf{'}s not
0 we divide so imagine we have a function of this type double to double
to double because now we need curried functions so now we can just
write code like this F safe divides 2 1 safe divide for 2 and another
test is we want to create a validated case class so what we need to
do is to have a current class constructor now the ordinary classical
structure would be uncared it will take a pair of arguments what we
need is 2 so this will be C to apply so this is the ordinary class
constructor with two arguments and dot curried is a standard method
on a function in Scala so this is in the standard library and the
result is a function of type double - double - C - which is a constructor
of the type C - but it\textsf{'}s clarity so now since it\textsf{'}s carrot we can just
use like that and we can use it like that so in this syntax we don't
need to call map - for example directly we just write if these are
directly applicable this is 2 divided by 1 this is 4 divided by 2
we could just implement safe divide as a syntax as well if we wanted
to and then we would have code that\textsf{'}s maybe easier to read in any
case now we can see that using the method app and in the syntax so
it\textsf{'}s basically app which is defined as this kind of function it\textsf{'}s
it becomes easier to write code with the clickety factors so this
app seems to be an important method that is simpler than F map - or
map - it allows us to define nap 3 in that 4 and so on and actually
it allows us to write code quicker without explicitly calling those
earth map three if not four and so on so basically what we have found
is that F map - can be defined through app if we have app using this
code and we just use F map F and then we apply up to the result that
was our code essentially defined first we do f9f of this and then
we apply up to the result to do this so that\textsf{'}s what we just found
now can we also define app through F map - yes and the way to do it
is to set a the type parameter a here to be the function B to Z we
are allowed to do that because these parameters are arbitrary so we
can just have a special case where a is equal to that and then we
here we would have a type like this be to Z going to be to Z so we
have an identity function of this type always and we can just apply
F map to to that identity function and the result would be a function
of type FA - FB 2 FZ but a is B - Z so the result will be of type
like this and so that\textsf{'}s just F map to applied to the identity function
of this type now because we have defined the type parameter a through
B in Z we have one fewer type parameter in app only two type parameters
in app or as is in F nap - we had three type parameters so it is in
this way that F map - is more complicated than the app so actually
F map to an app are computational equivalent we can define F map to
through app we can define up through a snap - and this diagram illustrates
how that works the type diagram starting from FA go by F naught F
F lowercase F has this type so if mapping it over F a gives you f
of B to Z now you app that you get this function of B to F Z or you
can directly F map to from here to here and that should be the same
and so clearly app is equal to something like F map - of identity
if this is identity so if we take F to be identity then this arrow
is just identity here so these are the same and therefore then app
is the same as f map - over identity so this diagram shows you at
once the two equations the expression expressing of f map to through
up and the expressing of app through F negative and similarly we can
define F map three of my four and so on and here\textsf{'}s a diagram for ff3
it is slightly more complicated because we need to first map to this
then we need to do app with these type parameters and then we need
to do app on this argument we need to take keep this argument constant
and app on this argument with another cz so in order to do that we
need to f map in other words we need to lift up from its ordinary
type which which is this into this type which is kind of a reader
monad with this as the environment so that as a reader functor F map
yeah so so this diagram shows how f map 3 is really defined but in
the code we don't need to worry about this because it\textsf{'}s automatic
because we already carry this argument so we don't need to explicitly
F map when we use the in fix syntax which we have just seen in the
code I would like to call your attention to this pattern that we have
seen before that we have some kind of equivalence between two functions
or two methods and the equivalence works by taking F map and and composing
it with one of those methods and usually one of those methods is a
natural transformation and another is a kind of lifting so we have
seen this pattern several times before where we were able to get two
functions that are computationally equivalent but one is simpler than
the other because there\textsf{'}s this F map but one of these functions already
does and the other doesn't so this function becomes simpler it has
fewer type parameters and fewer arguments so let\textsf{'}s recall the zip
operation that we have seen before and let\textsf{'}s see how that operation
is related to map to to find that and also let\textsf{'}s think about these
two types that are equivalent and their equivalents is given by the
curry and unclear methods in the scholars can standard library as
we have seen so we can take this F NAB tool that we had in the previous
slide the sect map to and we can unclear it and if we incur it will
have a type signature like this which is a tuple and here is also
a tuple so now let\textsf{'}s do the same trick we did in the previous slide
when we substituted an identity function into this F map to in order
to obtain a simpler natural transformation so in this case the identity
function will be of this type rather than what we had before we had
before was this type but we carry no sorry we uncaring now so instead
of a function type will have a tuple type like this so let\textsf{'}s let\textsf{'}s
do that and the result will be we have F map to with this now we take
C in other words equal to the tuple 8 or in B so we set the type C
to be the tuple a B and then we have a function of this type which
is FA of be going to F it'll be because C is tuple a B now this function
is called zip because it\textsf{'}s a very similar type signature to the standard
function zip different sequences where you take two lists you zip
them and you obtain a list of pairs so here F is the list type constructor
so then zip function can be seen as taking two lists of maybe two
different types not necessarily but maybe and returning a list of
pairs so let\textsf{'}s check that again zip and F map to our computational
equivalent so we define zip like this can we define F map to value
zip yes all we need to do is we first need to do zip that will give
us this and then we need to apply F F to F which will take F a B into
F C so this is the type diagram that illustrates this so we do is
if we get that and we apply enough map F and we get F C or we can
go directly from here to here using F map 2 or F which is the uncut
version so this diagram at once expresses the equivalence of the two
equations here because you can take this to be identity this function
and when we do that these two become identical because F map of identity
is identity by the factor law therefore these two are identical and
so zip is equal to F map to all that F of the identity so that is
this equation and otherwise you get the second equation so we can
think now that applicative functors that were initially defined as
something that has mapped to could be equivalently defined as something
that has zip of course work or something that has out there was a
roster equivalent and certainly laws should apply and hold but we
will look at Louis very shortly we could call factors a pebble if
this zip function exists for it and that would be actually weaker
than an applicative as we will see but there doesn't seem to be like
a good name that everybody uses for functors that just have the zip
method and nothing else there are typeclasses for that in different
libraries are called differently for example in the cats library it\textsf{'}s
called semi Drupal in this ecology library it\textsf{'}s called apply or something
like that notice also the same pattern which is a natural transformation
is computationally equivalent to lifting and the second one\textsf{'}s certainly
needs to be demonstrated rigorously we have not done this in the slide
here also have not done this we have indicated that they are defined
through each other but that\textsf{'}s insufficient to show that there are
computationally equivalent you have to show that this is actually
they're isomorphic in other words if you take app define F map to
from it and you take that off map tool and define a new app from it
then you have to show that that new app is the same as the app you
started from similarly here you would need to show that if you take
a zip say and you define as map tool through it and then you use that
F map to to define a new zip then that new zip will be exactly the
same as the own zip that you started with and you have to also show
that if you start from F nap to and go in the other direction F map
to define zip you find new f-type to ensure it\textsf{'}s equal to the old
F nectar now these proofs are very straight forward and we have seen
one of these proofs in a previous chapter in detail so I'm not going
to go through them again especially since it\textsf{'}s exactly the same pattern
where two functions are equivalent and they differ by applying I compose
a composition with F map F so this is a pattern that we have seen
time and time again and so it\textsf{'}s sufficient right now to recognize
it and understand that the proof is exactly equivalent analogous to
the proof we have seen in chapter 7 I believe where this was written
out in full is this equivalence proof finally we can also ask are
the operations app and zip equivalent they seem to be two sides of
the applicative coin indeed they are in order to figure that out let\textsf{'}s
remember that we started out by setting a to B to C function so let\textsf{'}s
do the same with zip we will get this transformation this is what
zip does now can we get an FC out of this and if we get if we do then
we will get an app because app is basically this going to this going
to FC so we could just carry this to get the correct type signature
for app if we could only convert this into an FC now obviously we
can convert this to FC because this is a function from B to C and
we have a B so you can clearly just apply this function to this B
and get a C let\textsf{'}s call that function eval which is this function and
then f map of eval will be a function of this type it is trivial to
define that function then we just do F map of it and we get this so
then we transform from here to here and we just uncurl we get an app
ID write it with two piece just so that it\textsf{'}s different name from app
but this is just the uncured version of app so the the uncured version
of app is equal to zip composed with F map of evil so we see young
exactly the same pattern that app is a zip with some F map although
it this is not an arbitrary function it\textsf{'}s a specific function but
it\textsf{'}s a very similar pattern and so it suggests computational curveballs
so let\textsf{'}s try to define in the other direction how to define zip through
app well that\textsf{'}s done like that so app and its functions that operate
on two different types instead of zip let\textsf{'}s prepare for this we would
need a function that makes appear out of two elements so let\textsf{'}s call
this function here and f map of parallels just denote f map like this
for brevity which I have already done in in previous chapters seems
to be a good notation and then clearly we get this kind of situation
if we apply this F map of pair to some F a of type F of a and we get
this and that is something that now resembles what app likes to take
as a as an argument so then let\textsf{'}s see zip of two different values
of a and F be you'll be equal to app applied to a pair so app has
this type signature we need to give it a product F b2c is this where
C is a to B and this is FB so then applying that app we get F C and
C is a to be so that\textsf{'}s exactly the right type namely F of a times
B so C is 8 times B knotted with sorry C is a times B and so we have
expressed zip through F and we have expressed up through Z and here
is the type diagram we need to take care about what types were using
so that\textsf{'}s why I have written about all these types in foam here the
type parameters for app for example you see app is defined like this
but now we need to use as its first type parameter we need to use
actually B to C so {[}Music{]} actually you know that is a mistake
sorry this needs to be deleted a because it\textsf{'}s not a B to C B this
is AB BC because this is how I defined it so this is just a PC I will
correct this slide so we start with this type we do a zip on it we
get this and then with your F map of eval and then we get F C or we
start with this type we do an app on it which is going to give us
F C directly so I need to delete these two symbols and then and also
these two symbols and then this diagram will be correct and these
type others are correct so clearly we can also do this with carried
arguments we just need to define current versions of zip which which
is like this and then we have exactly the same relationship between
up and fzp so I just call this F zip where it\textsf{'}s great and then f z
PQ is that and it\textsf{'}s exactly the same except we don't need to do the
two plane of arguments that we just need to use the arguments one
by one and now we see that this function takes this argument and this
function also takes that argument and so we can carry that away we
can omit the argument Q and we can write it like this which is nice
because it allows you to reason quicker about what is equal to what
you would have to write fewer symbols you see we can also omit the
argument P because this is now app of pair of P which is firstly apply
pair and a new clean up in my notation let\textsf{'}s function composition
in Y notation goes left to right and here are the explicit type parameters
that you need for this to work having looked at all this we still
don't know what the laws are now we have mapped to we have app and
we have zip let\textsf{'}s now derive the laws for these methods the motivation
for laws comes from our initial idea web map tool is basically a replacement
for a monadic block or a functor block with independent effects and
in other words map two with two arguments and a third argument which
is a function replaces the functor block of this comment so we started
with this we expect their fourth that whatever laws of the Monad hold
for this kind of construction should also hold for map 2 therefore
we just will take moon at louis which we considered in in the previous
chapter and write them replacing the functor block with map to where
where we can so the first two laws to consider are naturality laws
they come from manipulating data in one of the containers so for example
we can manipulate first in this container and that should be the same
as if we acted with the function f on X like this so if we rewrite
that in terms of map tool when we get on the left we get this map
to of this and this and of G on the right we have map to of this and
this and a modified G which takes X\&Y and returns this and similarly
if we apply map on cons to instead of count one we will get the right
natural T law which is like this very similar except acting on Y instead
of acting in X here also the monads have identity laws and associativity
laws so let\textsf{'}s look at those the associative law is that we can inline
the generators in a four yield block or a functor block that is the
right hand side and that should be the same as when we in one when
we write all of these in a single flat for yield block and we can
inline in two different ways and that should be the same so that that\textsf{'}s
the associativity law for the Monad now if we really write that so
the idea is that we have three containers and we have a function of
three arguments let\textsf{'}s say and then we first go over the first container
and then Y Z go over the second container now we need to do this rewriting
because we we need to formulate everything in terms of for yield blocks
with just two lines because that\textsf{'}s map to and for yields blocks blocks
that don't depend on containers don't depend on each other on previous
owners so this is a map - and then this is also a map - so we have
a map - of count 1 and map - of Constituent 3 and then the function
that just takes two arguments puts them into the tuple that\textsf{'}s the
Scala syntax for that and then the function that takes X \& Y Z and
returns G of X Y Z so we need two unto pole like this as the result
of map tool will be a tuple on the right we first apply the for yield
block to container 1 and 2 and so this becomes mapped to of point
one con 2 with the two-point function and then we do map 2 of this
and country with this function which now has two n tuple X Y first
so therefore this is the associativity law for map - let\textsf{'}s consider
the identity laws identity laws expressed in the relationship between
map 2 and the P were united so it appears that applicative factors
also need the pyramid it\textsf{'}s very useful to need to demand that the
pure method exists and satisfy the identity laws turns out that this
constraints so negative factors in an interesting way a useful way
without identity laws they're just too many ways in which you can
define not to satisfying just associativity law so the identity laws
are that if you do a pure on the right hand side that\textsf{'}s the same as
if you just had X equal to a because that\textsf{'}s an empty context or empty
effect so then we have the left and the right identity laws because
the pure or the empty context can precede a generator or it can fall
it can follow a generator service on both of these cases we have this
equivalence and so these two laws are written like that so for example
here is a map to of pure a and the container and then the function
G and on the right is just a simple container map with this function
that substitutes a instead of X and similarly the right identity law
so now let\textsf{'}s derive the laws for zip the reason we want to do it right
away is that these laws are quite complicated so these are very complicated
combinations are all kinds of things that are complicated so basically
map two of conto on map two of County two point three that is simple
so you just change the order in which you apply map to but everything
else is just some kind of bookkeeping that we should be able to get
rid of and simplify somehow so for example we don't want to talk about
arbitrary function G in the law we'd like to simply find that so that
law doesn't contain arbitrary functions so we have seen before that
this kind of simplification can be obtained if you instead of lifting
as you consider natural transformations and so that\textsf{'}s computationally
equivalent but the laws are much simpler we have seen that before
that\textsf{'}s for example the laws for flatten in the Minard are much simpler
than the law for flat map a lot of point but it\textsf{'}s the same thing will
happen here and it\textsf{'}s reasonable to expect that this will happen so
let\textsf{'}s do that and derive the laws for zip so what are the natural
T laws now naturality laws written like this we here needed to deal
with this kind of function where we modify the function by taking
some arguments and so on now it\textsf{'}s not very nice to reason about such
functions so I would like to introduce a short notation for that the
source of difficulty or the source of lack of elegance is that we
need to write these arguments and then all we do is we put these arguments
right back into the function G except one of them gets modified so
whatever we need to modify both so that\textsf{'}s something we would like
to be able to write more concisely and so that\textsf{'}s why I introduced
this notation so first I need use this function product notation which
is a function on a product defined like this so this is just syntax
so to speak and this function is trivial and doesn't let me do very
much but using this notation now we can do a lot of interesting things
for example we can now rewrite the laws from mapped like this F map
tool is just map to where the first argument is the function with
this type and the second argument is a tuple is like as a pair just
swap the arguments as compared to my job now this is the short notation
for first container dot map F you see that then it\textsf{'}s a map to with
this tuple so we read that as a product like this and on the right
hand side it\textsf{'}s a lab two of that tuple unmodified but the function
G is modified in that the first argument gets acted upon by function
f and this is expressed like this in the short notation so we have
a function composition on tuple so this is a function that acts on
the tuple a B and this function applies F to a and identity to be
so that\textsf{'}s a function that takes a tuple a B and returns a tuple F
of a B and then we apply G to that therefore we get G of F of a B
that\textsf{'}s precisely what we have here and so therefore this notation
can be used somewhat shorter then the code and easier to reason about
so these are the two laws that we have so far for natural T this is
the associativity law where I just have this notation G 1 2 3 G 1
2 3 to indicate that this is the function G with three arguments but
this second and third arguments are in a tuple and here the first
and second arguments are in the tuple so I have just rewritten associativity
law in a short notation it\textsf{'}s slightly shorter than this but it\textsf{'}s still
quite ugly and finally the two identity laws which I rewrite like
this pure acting a and then tuple with Q and then this function and
so on that\textsf{'}s exactly the law here and then I write Y goes to jr. a
1 as B goes to G of a B so these are the laws for map 2 so let\textsf{'}s Express
F map to through zip we can express it certain like that written out
with all the arguments in folds like this F map to acting on G and
also acting on this tuple is zip followed by lifted G or F map of
G acting on this tuple and so since this tuple is the same we can
omit that argument in the cred equation where the both sides of this
equation are now functions acting on a tuple q1 q2 so this is how
we can express F map through zip and we can substitute this F map
into the laws and then we will obtain laws for zip to simplify things
we can combine the two natural G laws into one where we use two functions
F and G or F 1 and F 2 acting on Q so that\textsf{'}s how we can rewrite these
laws and naturality then follows four zip because F map G is zip followed
by lifted G so we can just write it here and the right-hand side of
the natural law is zip of this followed by lift G so now you see we
have this followed by left G equal to this followed by lift G \& G
is an arbitrary function so clearly we can just substitute G to be
identity and get rid of it so that\textsf{'}s therefore the cat\textsf{'}s reality naturality
well for zip if this law holds we can add an arbitrary function like
this and we restore this law so therefore the laterality low for zip
is equivalent to the natural go for f- so what does this naturality
law say it says we can first transform both arguments of the tuple
using some functions and then we can zip them or we can first zip
and then we can transform both arguments of the tuple using some functions
that\textsf{'}s a typical form of the natural reality law that says you can
f map something before your natural transformation or you can f map
it after natural transformation the results are the same let\textsf{'}s look
at the associativity law it\textsf{'}s more complex but if we do this substitution
so we take that law as written here and we just substitute F map G
as zip followed by lifted G everywhere so the result is that we have
G of zip and so on equals that so the arbitrary function G has a different
set of arguments on the left and on the right now you see as G 1 2
3 was actually this kind of function where we first I'm to pull 1
and 2 and then we have 3 or we have firstly on tuple 2 and 3 and then
we have 1 so this is what I am indicating in this very informal notation
I don't want to write a lot of parenthesis and so on I just want to
indicate what we want so this is just shorthand for kind of function
and that kind of function but if we substitute zip followed by G here
so now we'll have zip followed by G which means that we actually need
to substitute the full term zip followed by G on the queue so zip
on that followed by G that\textsf{'}s how every written it here now these identity
sorry these tuple transformations all come from this isomorphism which
is trivial that\textsf{'}s just we can undo pull this or we can untap on that
they're equivalent so let\textsf{'}s not have to let\textsf{'}s let\textsf{'}s not write all
of this explicitly every time we are on to playing and so on let\textsf{'}s
just do it when needed whenever we have a tuple of a tuple like this
we just unto pull and rearrange as required and this operation i want
to denote by a special symbol so this is the symbol which is kind
of equivalent it\textsf{'}s not precisely equal but it\textsf{'}s equivalent up to this
a trivial isomorphism so in other words very simple isomorphism that
doesn't require a lot of work and so if we get rid of that then the
G is an arbitrary function so let\textsf{'}s substitute identity instead of
G and the result is this law so we first do a zip on q1 and the zip
of q2 q3 or you first do a zip on q2 q1 q2 and then zip of that and
q3 and these should be equivalent up to rearranging the tuples like
this because the types are going to be different so let\textsf{'}s look at
the type diagram to see what types they are this type diagram is quite
large and so let\textsf{'}s look at look at it in this way so it starts from
these three if a FB FC which I have put into the diagram in this order
just arbitrarily it doesn't really matter now the first thing we do
is we make tuples say of FA and FB that that is indicated by these
two arrows so this is just to make a tuple out of these two also we
make a tuple of B and C here then we apply zip to fafb we get F a
B we apply the epitome of bit of C we get F BC now we can make a tuple
from this and this we get this tuple we make a tuple from this and
this we get this tuple now we apply zip again to this tuple so this
gives us F of that and this after applying zip gives us F of that
now actually they are equivalent to some F of this because of this
isomorphism so this corresponds to that and this corresponds to that
so this is the associativity law for zip its identity laws have complicated
form in particular because we have this arbitrary value a and actually
we can simplify them if we replace this pure emitted by an equivalent
method that doesn't have an arbitrary value a which is an interesting
trick actually so let me explain this simplification in some more
detail because this is a kind of a complicated law we want to simplify
it so here\textsf{'}s how we simplify it let\textsf{'}s consider pure of the unit just
apply pure to the value of type unit there\textsf{'}s only one now you have
that unit let\textsf{'}s apply we get a value of type f of a unit so I called
it w u because it\textsf{'}s a wrapped unit it\textsf{'}s a unit that\textsf{'}s wrapped in the
type constructor F in some way so with empty effect so it\textsf{'}s an empty
value unit wrapped in an empty effect so that\textsf{'}s why I called it wrapped
unit now it\textsf{'}s a pure of one so in order to restore the pure function
all we need to do is to map this one into a inside the container F
so that is what we need to do so in order to express pure through
wrapped unit so these are equivalent you can see that if we use wrapped
unit instead of here then things are actually certified and this is
how we do it so let\textsf{'}s substitute first instead of pure a we substitute
this now this we rewrite using this notation because argument B is
unchanged and instead of one we have argument a so we will call G
on this so you see so this actually is equal to that no way we can
pull out out of zip we can pull out this function using left natural
reality and then we get zip of W u cross Q where this now is outside
the zip it needs to act on the first argument and so this is how I
express that this function needs to act on the first argument of a
tuple second argument of a tuple is unchanged so now it looks like
we have a lot of this bookkeeping where we just put units and so on
so let\textsf{'}s denote the these things temporarily just so that we can reason
about that a little shorter so fine is this function and beta a is
this function so this is a trivial kind of code that just adds unit
and this code just takes a two of unit and B and returns a tuple of
a and B given a fixed value a so just substitutes a instead of unit
and the B is unchanged so this identity function is acting on B and
this function is acting on unit and this product this function product
gives me a function of this type so now this function is a composition
of this kind because we we first take a B we apply feet fight to it
which gives us 1 B so 1 times B when we apply beta a to it which gives
us a times B and when we apply G to it so that\textsf{'}s exactly what\textsf{'}s happening
here if we use that the advantage is that these are function compositions
we can reason very easily about function compositions so if we substitute
into that naturality law which we just had in this form then it becomes
G so this is beta le this is actually beta in my definitions of G
beta a zip now clearly data a can be composed with G and then lift
it because that\textsf{'}s just a functor law that we can lift after composition
and then the right hand side of the natural T of the identity law
like this which is what we simplified here as this composition therefore
the naturality law sorry the identity law becomes this equals that
but here we can also put Phi inside so we can lift Phi first and that
would act on the Q first so now we have an equality that has a common
prefix of some functions we can commit it and the law becomes much
simpler it\textsf{'}s like this so now Phi is this isomorphism between B and
the tuple of unit and B again this is a kind of a trivial isomorphism
but we can apply whenever needed we don't want to keep writing file
all over the place if I lifted to F is the neither morphism between
these two again what\textsf{'}s imagine it is applied whenever necessary we
will express that using this symbol but these are not really equal
but they're equivalent up to applying these isomer films isomorphisms
whenever necessary so the left identity law therefore can be rewritten
like this and the right identity law similarly like this so then let\textsf{'}s
actually simplify the notation some more {[}Music{]} instead of zip
of PQ let\textsf{'}s write this now this is just a symbol I invented it doesn't
matter what it is but it\textsf{'}s kind of a zip zipper symbol if we write
it like this then associativity and identity law look like that now
these laws are basically laws of a monoid up two different types that
I did not write so this is of type FA the size of type FB because
of type FC and assumed transformations that are isomorphisms here
and here natural reality law is written like this so you can lift
F act it on q1 lift f2 acted on q2 it\textsf{'}s the same as if you lifted
this and acting it on the Zipp now the wrapped unit has no laws at
all it\textsf{'}s just a fixed value of type F 1 F of a unit the natural reality
law for pure will follow automatically from the definition of pure
through the wrapped unit this is again the pattern we have seen where
one covalent method is simpler than another and it is it is equivalent
nevertheless and the other method is expressed through the first method
using some F map so that\textsf{'}s very similar tangent and so actually we
see that the laws of applicative have become extremely simple and
suggested there similar to the loss of a monoid there is a social
activity and to identity laws now this syntax of code is just zip
right so this is P zip Q in Scala you can write zip in fix notation
already so you can just say q1 zip keep to zip q3 and you shouldn't
you don't have to worry about parentheses that\textsf{'}s the essence of the
associativity law and identity laws mean that you can have enough
something that you zip with and it doesn't change that then you're
zipping with up to and isomorphism of course it\textsf{'}s they're not actually
equal they're isomorphic they're equal when you apply those isomorphic
transformations in the right places so obviously this is much simpler
than the laws when formulated in terms of map to I already discussed
in a previous tutorial that naturality usually follows from parameter
ECT in code that has type parameters so when we want to check laws
for specific factors then we don't usually need to check naturality
it will be obvious if our code is fully parametric and generic and
all type parameters then it will natural tea will be automatic associativity
of course needs to be checked and identity laws need to be checked
so actually it\textsf{'}s interesting that we have not seen third natural to
move from up to we have seen to natural reality laws and we have derived
naturality laws per zip but actually when we define map to three zip
there\textsf{'}s an there\textsf{'}s one more law one more natural T law to we'll see
shortly and now it became obvious that we are we were missing a law
so our consideration when we derived the laws they gave us two laws
but they didn't give us all all the laws we could have been more clever
right here but we weren't however once we understood how to formulate
the laws in the best way then obviously the right thing to do is to
start with these laws and then derive the laws from map to from those
this also gives us assurance that we haven't missed any laws this
is a very common construction I'm annoyed and generally this idea
of having a social tivity laws and identity laws is a very is a very
common pattern that happens time and again once we see that we have
assurance that the laws are complete this is the complete set of laws
for an applicative functor if we formulate the laws in terms of zip
zip and wrapped unit so we have now great assurance that we are on
the right path we have found the correct laws for duplicative factors
now factors that are zip able as I said before they did not have peer
necessarily they do not have wrapped unit they only have the associativity
and naturality laws but negative factors must have both this and these
laws so as I started from monads well clearly if a functor is a monad
then it will satisfy all these laws - if we define map - through the
mullet construction then we will automatically satisfy all aplicativo
since since those laws were motivated from monadic clause but there
are some applicative founders that cannot be monads and so actually
all monadic factors are negative but not vice versa and this is actually
a mistake it\textsf{'}s a strict superset so there is strictly more applicative
functors than Muniz and as another way in which negative factors are
a superset is that bucket of fun term employment asian may disagree
with the moon and implementation of the function map - in other words
we may want to define lab - and zip and so on in a different way for
a functor that already has a monad implementation but for some purposes
we might want to define it in a different way and we have already
seen that in the first part of this tutorial when a monad would for
example for the either factor and one odd implementation would take
only the first error in a computation and we want to gather all errors
so we define an applicative factor differently so that it collects
all errors so that definition is disagrees with the definition of
map - that would follow from the walnut so strictly speaking we should
rename this factor some and into some other name just to distinguish
it so that we don't get confused because we might want to write applicative
code in the magnetic for yield block and then they would accidentally
have the wrong implementation of map 2 so strictly speaking we should
avoid defining map 2 at the same time as a flat map so that they disagree
but in practice this does not happen very often but it but this is
another way in which applicative factors are a strict superset so
sorry about this mistake it\textsf{'}s a superset so what is the third natural
T law it\textsf{'}s a law where we transform the result of map two we have
not done this we have not thought of doing this transforming the result
of map two should be equivalent to doing map tool like this and transforming
the result of G so when we write it in terms of map two we get this
curve once and if we write it in a short notation then map 2 of G
followed by some lifted function must be mapped to of G on which we
act with that function or if we rewrite the same thing by substituting
explicitly the arguments P and Q which are here count one and count
two then we get this now this law follows automatically if we define
map to through Z because that\textsf{'}s a definition map 2 of G is this but
then clearly if we apply some function f to the result then it\textsf{'}s the
same as if we lifted a composition of G in F because this is the functor
composition law so this is a very obvious property then that is not
reality with respect to transformation of the result of the map so
we could have noticed that we're missing a naturality law firm map
- if we looked at map - type signature we see it has three type parameters
and usually there is a natural T law for each type parameter because
nationality law means we aren't we aren't changing the results of
any transformations applied to a certain type and for each type parameter
we can transform that value of that type separately from transforming
values of all other time parameters and so zip has two natural G laws
because it has two type parameters but my up two has three type parameters
that should have three naturality laws so that\textsf{'}s the third natural
table now I would like to go a little deeper in analyzing what the
properties of app turned out to be so that\textsf{'}s a very interesting direction
because it will show us more deeply what are the properties of app
and what are the laws of app now the laws of app are not so easy to
derive and we will have to prepare ourselves for that so app is a
function of this type now we can consider it as a kind of lifting
so we have this function and we lift it into this but actually this
is not a function this is a type constructor whose type parameter
is a function type so this is not really a lifting of a function into
some other functor but we can think about it like this we can think
well this is just like a function it could be except it\textsf{'}s a little
twisted so it\textsf{'}s kind of a lifting from a twisted function type into
the function of a type constructor to type constructor type now a
lifting should have identity and composition laws just like a lifting
of a factor the factor would have type signature a lifting from F
map going like lips a B to F a FB so that is a classic lifting where
we get our intuition about lifting now lifting in the functor case
has identity and composition laws so just two laws which means that
if we lift identity we get identity and if we lift composition of
two functions we get a composition of two functions that\textsf{'}s very reasonable
can we find the same laws for this lifting can we find identity and
composition laws for it now if we could then we would first of all
need a value of this type F a to a which would represent the identity
for for this lifting and then it would we would demand the function
takes that identity value and returns an identity transformation on
a PHA so how do we get a value of this type well let\textsf{'}s call it by
this symbol identity with this dot in a circle well we have a pure
method on an applicative factor so we can easily create an identity
transformation like this and put it into a pillar and that would be
a functor type value with empty effect because we're pure we were
using pure and identity transformation so that looks like a good candidate
for the kind of value that should not transform anything we will see
that this is indeed the case now the second question is how do we
check the composition lon well unusual functor lifting is clear what
the composition of two functions a to B B to C they compose only and
get a function e to C similarly here you can pose a fail to FB FB
to FC and you get FA to FC so here we have this type however so how
do we compose this and this so that the result is this well it is
not easy to do that necessarily but let\textsf{'}s try to use map to to implement
that composition can we maybe do that because we almost have it we
that we need with map to or we could use zip maybe zip is actually
even easier to visualize here if we zip this this we get an F with
a product a B and BC we can just compose those things in the product
and F map so that\textsf{'}s what the f map 2 gives us in one go with it takes
two functions P and Q now let\textsf{'}s denote by this symbol this kind of
twisted composition where we can post this with this and yield that
so we will define it now using this code which is f map of G H F map
to of G H where the function takes a to B and B to C and returns just
a composition of these two P compose key P and thank you now it seems
that we have defined a reasonable candidate for identity and the reasonable
candidate for composition let\textsf{'}s check the laws what are the laws well
it turns out there are precisely the laws of identity and composition
namely these the composition of this identity with something does
not change that something and composition is associative also there
are two naturality laws which basically say that f map or lifting
plays well with this composition if you can lift first and then you
compose or you can first compose and then lift this and act on the
result and so so you can you can check that these types make sense
the first three laws or actually the identity and associativity laws
of a category where the morphism type is this twisted function type
the identity is this and the composition is that I remind you that
the category laws for identity and composition laws you need to have
just these laws associative 'ti of composition and identity laws the
second the last two laws are natural reality was there connecting
this twisted category composition with the ordinary F map which is
the ordinary lifting that the F must already have because F must already
be a factor so these are the five laws that are very interesting because
they show that app is actually kind of a lifting is it satisfies functor
laws as if we had a functor between these two categories so in this
way we have justified calling up and lifting it\textsf{'}s it\textsf{'}s it\textsf{'}s like a
F map function except the category has a twisted type this is another
way in which we have assurance that our set of laws for the applicative
functor is reasonable it is not too large not too small because this
is just a category law in some suitably defined category in other
words in a category of functions with this type morphisms of the category
have this type I remind you what I call categories just morphisms
where this arrow is just a general symbol and you have to define what
it what it is in any particular category and then you need identity
laws and Composition laws which are these so having defined that let\textsf{'}s
check that this is actually true I haven't actually derived that these
laws must hold they are follow they follow from the map to laws so
I I will now go through this derivation for example let\textsf{'}s start with
the identity was let\textsf{'}s consider this we substitute the definition
of the product dog sorry of the composition which was here and also
we need to look at slide 7 because that defines laws for the F net
so if we substitute that we get F map to of this which is list definition
here but we are working on pure of identity function so according
to the law on on slide 7 this is equal to that so we have F map to
of something and pure so that\textsf{'}s supposed to be equal to this so let\textsf{'}s
just copy this over and we get that but now you see identity function
followed by B is just B so now we have be going to be which is an
identity function lift that and still an identity function so that\textsf{'}s
equal to H so that\textsf{'}s why they are tentative or holds similarly we
derive the right identity law associated with T law we also need to
substitute then according to the third naturality law now this I'm
just using a very short notation where this is a function that takes
two arguments and returns the composition of these two arguments as
functions that\textsf{'}s what I want to use here this is this function this
I just denote this by that it\textsf{'}s a single now we use the third naturality
law and move the function this function out of f map to so then F
map to with this function H K is equal to this function lifted of
have not evolved identity HK so that\textsf{'}s the third naturality law and
once we do that we can do we can just see that whenever we have the
category composition it\textsf{'}s just basically f map of this composition
function and so then every time you have this you have a composition
so then you basically have F map two of these and this is mapped to
that and that is mapped to that but this is basically the same as
a formulation of a socially divisive o4f map to where we had to use
these functions that rearrange the tuples now this function is the
same this is the G in the F map to law here this is the G and these
are precisely the right hand sides and the left hand sides of this
law this is that and that precisely that long and so because F map
2 has that associativity law this must be equal to that because so
we find that these are equivalent so so associative et offereth map
to a group is equivalent to relativity law for this the naturality
laws can be derived by writing out again what is the morality law
for map tool that we have now three natural tables come up to so for
example you do this you act with something on G we write a definition
of the category composition there is no name for this category by
the way I don't think there is but I just think about it as the category
allows me to think of applicative factors as having a lifting sometimes
it\textsf{'}s just a category where this is the composition so this becomes
my left hand side and then I can transform it so just put this outside
put this function outside so I get that put it in here and I have
GH then I I put that is the is the mother this F map to of this alright
I have another naturality right where I act with some function on
the G so that\textsf{'}s the third natural T so I can pull this out of F map
to which is this part I pull it out with and the result is that I
have just XY going to X and then Y which is this so then I pull this
out and this is a definition of G dot H so then I have my natural
to look for yo dot H and similarly the other natural tool so now the
laws for app let\textsf{'}s write them out so app has this type and is defined
like this identity law is that app of identity is identity right so
the laws for app are just the laws of of lift and we like that lifted
identity must become identity and lifted composition must become composition
so these are the laws for app identity law let\textsf{'}s derive it well we
can derive it in a pedestrian way and let\textsf{'}s do it first so app of
identity you applied to some Q so what is that so let\textsf{'}s write the
definition let\textsf{'}s f map of identity and then this is a definition of
this single applied to Q so let\textsf{'}s write it all out we have this F
map two of this functional identity of this type is actually this
function if you think about it but we uncured it so we we need to
incur it because we want to have map to which is uncured you see here
I have this F map subscript to just clear it and F map without substrate
is uncared applied to a product of F X is just this this is equivalent
to this identity and now I'm going to just simplify this by using
the identity law firm F map to which is going to give me this if I
substitute we identity law for F map to which is this and therefore
I have this code now identity of X is just X we have X to X lifted
still identity the result is Q now there\textsf{'}s an easier derivation which
I would like to use now because it\textsf{'}s interesting and simpler consider
these isomorphisms they are obviously they are not the same obviously
because this is a value and this is not yet evaluated you have to
give it an argument and so on but they're equivalent computationally
and then this app becomes basically after this equivalence if you
look at this app it basically becomes a categorical composition of
Q and P so Q has this type you cannot do categorical composition unless
both have function types but because of our P isomorphisms we can
replace a by 1 to a here and so we do that this must have been a double
arrow I will correct the slide so Q F 1 to B can be composed with
pfb to Z and you get something of type F of 1 to Z which is equivalent
to F Z so that\textsf{'}s F Z so that\textsf{'}s in this way we can equivalently rewrite
app as just this categorical composition and then everything becomes
just very easy because then app of identity on Q is Q composed with
categorical identity and that\textsf{'}s just Q by categorical laws so composition
law again they are easy we say AB PQ is just Q P and we just rewrite
that as q GH and then this is where rewritten as app of each of app
of G of Q which is f of h q g q GH now these are equivalent because
of associativity so in other words once we establish the category
laws app becomes a lawful lifting and all the other laws follow so
it\textsf{'}s sufficient to establish the category laws or it\textsf{'}s sufficient
to establish the zip laws and everything else follows so these are
the all the possible ways of looking at the laws for placated functors
so we can choose the one you like best and different ones have different
utility for instance the category laws are not directly so useful
for for coding and they're not so easy to check perhaps because you
need this complicated categorical composition and all these type parameters
I basically have three type parameters in this composition which is
harder to check than zip that has two type parameters but it it allows
us to look at those things in a very general way which we'll see later
so now I will go on to define various constructions that you can use
to make applicative functors out of other types we have seen in the
previous chapter a large number of constructions for monads since
all monads are applicative they all those one etic constructions also
hold but sometimes they hold for weaker conditions in other words
not as an magnetic construction that for example this was also magnetic
construction but it requires both of them to be Mona\textsf{'}s but now we
only require them to be applicatives negatives is a superset of monads
so this is a similar construction but it is a superset and so on so
we'll now go through these constructions and show that the laws of
the implicative hold for each of them assuming that the laws hold
for the parts after which you build 

the first construction is constant factor and identity factor both
of these factors are also Mullins and their applicative instance is
following from the moon unit instance nevertheless let\textsf{'}s look at the
code the constant factor is a factor that takes a type parameter a
and returns a unit type so we could define it as this type function
that takes the type parameter and returns always a unit type independently
of the type parameter so that\textsf{'}s why it\textsf{'}s a constant factor it\textsf{'}s like
a constant type function now for the constant factor there\textsf{'}s only
one value that data can be if the data is of type F of a namely the
unit value and so all methods of the factor including monadic methods
flat map pure map zip we can only return the unit value since all
methods return unit value all laws are trivially satisfied because
the laws say that one combination of methods should be equal to another
combination but all of these always return the unit value so they're
always equal so in this case it is trivial we don't need to check
any any laws here let\textsf{'}s consider the identity function it\textsf{'}s a type
function that takes a type parameter a and returns the same type a
so you can look at it as a type function that is the identity function
at type level let\textsf{'}s define this type constructor like this let\textsf{'}s define
the factor instance there\textsf{'}s a standard very simple code that just
applies the function f to the data there is nothing else we could
do and let\textsf{'}s look at the applicative instance now I define this typeclass
that I called Mujib which is just a typeclass that expresses the implicative
property of the function f by defining methods wrapped unit and zip
i made this typeclass require a typeclass constraint that the type
constructor f should be a factor i also defined a pure metal because
we can now using the factor instance for f we can define pure through
wrapped unit i also define some convenience methods such as getting
the zip evidence value of this type getting the wrapped unit value
for a given type constructor so I can just write W U of F at any point
it\textsf{'}s very quick to get the wrapped unit value I also defined a converter
to catch- instance now on the CAD Slimer II applicative instance requires
pure and app but when you reason about the properties of Lickety factors
and when you check the laws it\textsf{'}s much easier to reason about functions
zip and wrapped unit then about alkanes pure and so they're equivalent
as we have seen but it\textsf{'}s much easier to reason about applicative filters
in terms of zip and wrapped unit so that\textsf{'}s why I defined this as an
as an adapter but I don't actually use the cat lick ative I use my
top class with zip instead and I also define a syntax it allows me
to say if a zip FB which is shorter and easier to read which is equivalent
to this slightly more verbose so to define a typeclass instance for
zip it is required to have a functor type of instance and so that\textsf{'}s
why I will always define first a functor instance for a type constructor
and then a with zip instance so how do we define a with zip instance
well we just need to define the wrapped unit the whoo and the zip
in this case the wrapped unit is just unit there\textsf{'}s no structure that
wraps here anything so it\textsf{'}s just unit so we have nothing else to do
except write these functions like this and we could have written them
using the carry Howard library implementing them automatically because
this code is completely determined by the types there is nothing else
you can do for example in order to return a value of type a tuple
a B if you're given a value of a and the value of B there\textsf{'}s nothing
else you can do in this so you could just say well this is shorter
than implement it\textsf{'}s the same let\textsf{'}s check the laws now the associativity
law says that this combination let\textsf{'}s undo my changes to see what the
code is since we need to know zip of a and the result of the zip of
FB and FC is just that and the zip and the other order is this so
we need to show that these are equivalent but this is exactly the
definition of equivalence which is rearrangement of nested tuples
so there is nothing else we need to do here to prove and similarly
identity laws and say that zip of wrapped unit and FA must be equal
to FA but wrapped here it is just unit and zip is just a tuple and
so this is a tuple of unit and FA and that should be equivalent to
FA but this is actually the definition of our equivalence that we
have equivalence that could rearrange two poles when necessary and
also add or remove a unit in a tuple when necessary so that\textsf{'}s just
a definition of our records so the laws are satisfied by definition
without much kind of calculation here consider now the second construction
this is a product of two factors so if two functions are replicated
then the product like this is a factor that is also applicative now
the product construction is seen in pretty much every typeclass in
the functors product of two factors is a functor monads product of
two minutes there is a moment filter balls product of two filter rules
as a filterable same as for application it\textsf{'}s a it\textsf{'}s a product is always
going to be a construction for every of these typeclasses however
the sum or the disjunction is not a construction for applicative so
the disjunction of two applicative factors in general is not effective
and also it wasn't so Ramona we'll see examples shortly non-intuitive
factors of this shape so let\textsf{'}s look at the code for construction to
now we need to define the type constructor somehow now we can't just
say type F of a because we want G and H as parameters the way around
that is to use the syntax of the so called kind projector in Scala
which I've been using in this tutorial and this is the syntax that
represents the type constructor that is the product of G and H so
it takes that type of parameter and returns this type so this is just
a syntax for type function written like this the lambda is a key word
that the plug-in defines so first we need to implement the function
instance here it is G is a factor H is a factor then we define a factor
of this so we need to define just a founder instance for product which
is a standard code that you take component by component the first
component of a fail you map in the second component of a fail you
map and these maps this is in G and this is an age so component by
component you define it the same way we define the rap unit and the
zip we defined component by component so for example zip from map
things like this we can just take this and this together which will
be the first component of each of them when we take this and this
together to zip which will be the second component of each of them
let\textsf{'}s just like that it\textsf{'}s the first value and the second value so
the first component on the first value is zipped with the first component
of the second value and you get this which is the first component
of the result so component by component we define wrapped unit in
Z the wrapped unit is just a tuple of the two wrapped units for G
and H zip is a tuple of - zips from the image this is in zip regime
and this is a fridge the walls will hold separately in each part of
the Pinner because the computations proceeded in each part of the
pair independently so the first component of the result depends only
on first components of the data the first component of the result
only depends on the first component of the data and so on for the
second component so it is kind of easy to understand the laws will
all hold very easily let\textsf{'}s nevertheless take a look at how that can
be written down so let\textsf{'}s write a social tickity so a pair of gah a
so I assume G X of type G of a and H a is of type h ma so I so this
will be of type F of a when F is this this type constructor we don't
use the name F here but I used it in the slide so if we first zip
the first two together and then take the result and zip it with G
CHC so what does it give you give us first we zip like this the first
two and then we zip the result with the rest now if we apply the definition
we need to zip the first component with the first component so that
will give you this now I stop you writing parentheses here because
this is the zip in the G factor which is associative by assumption
we already assumed that G and H have associated so I don't need to
write parenthesis like this I don't have to write it like this it
doesn't matter if I write it like this or if I write it like this
result is guaranteed to be the same already by circulating in the
function G so also here in the frontal H I don't write the parentheses
and clearly these expressions don't depend on the order in which we
zip so let\textsf{'}s {[}Music{]} let\textsf{'}s zip together the second two and the
result won't be like this we have this pair and then we zip it with
this ugha so again we zip the first component with the second with
the first endpoint the second component for the second component and
the result is this so we get exactly the same result after using a
social activity for G and H so that proves the associative law more
rigorously only identity laws are proving similarly we take the wrapped
unit which is defined like this by our code and we zip it with some
arbitrary GEHA and the result is the zipping of wrapped unit in each
component so we assume that this is equivalent to just gah a in each
component because there are the entity laws as we assumed cold for
G and H already and so this shows equivalence but we need this is
equivalence - yes and similarly we can show the right identity law
the 3rd construction is a free point advantage I already talked about
this in the previous chapter actually this construction as well as
this one of three constructions which I will talk about in a later
tutorial now it\textsf{'}s just a name that I'm using to invite myself to do
this and for this tutorial I am just using this definition this is
a factor Construction defined like this I'm not going to use the fact
that it is a free construction because we haven't yet gone through
this in the tutorials so for the function defined like this assuming
that G is duplicative we need to show that F is also implicated so
let\textsf{'}s see how that works so this is this factor again we will use
the kind ejector in order to denote this type construction and so
syntax will be like this since the type function that takes the type
parameter a and return the disjunction of either a or G of a note
that in the syntax for the type function a is a type parameter that
is only defined in the argument of this type function so this is not
a type parameter here it is not a type parameter of this function
it is a type parameter only of the type expression here so that\textsf{'}s
that\textsf{'}s important to keep in mind so I could use a different letter
here in principle and it\textsf{'}s not a type parameter in in the value here
so the function the factor instance is standard we take a function
f from A to B and we apply it to a here or to a here depending on
where we are in the disjunction and if we are here that we need to
map it over the G function so this is a melting the G factor so we
certainly need to assume that G is a function for this to work this
is Stanley let\textsf{'}s define the zip {[}Music{]} instance so I have put
here a type constraint so that they're both a with zip and a factor
and this is just so that I could more easily use map G if I ever need
it but it seems I don't really need it so let me remove it from from
here how do i define the wrapped unit and the zip so that\textsf{'}s actually
an interesting question because wrapped unit is required to be a value
of type F of unit which is either unit or geo unit so we have two
possibilities to implement this method we could have the left of unit
which is this or we could have the right of G of unit which is the
wrapped unit of G which is this so we could have either this or that
we actually I don't know up front which one is correct we need to
find out so it turns out that only this for fit fulfills identity
laws this one doesn't we'll see why very shortly but at the beginning
I don't know so you know that there are two possibilities you should
have to explore both of them how do we define the zip method well
as if needs to take either a G of a either B G of B and return either
of this a B G of a B so clearly we have several possibilities here
we can have a left left we can have a left right and so on so let\textsf{'}s
match on all these possibilities so we have four cases if both are
on the left and we have a value of type any and the value of type
B what can we return what we need to return a value of this type so
we could return the left of a be like this or we also could return
the right of G of a B where we could easily lift the pair a B into
the function G by using the pure method of the top of the function
G and very easily just left so the question is should we do that we
return this or we return a right of G pure of this turns out that
we have to return this in other words the identity laws will not hold
we'll see why now let\textsf{'}s see what happens when we have a mixed turn
left and there right now in that case we have an a and we have a G
of B what can we return well we can't possibly return a pair of a
B because we don't have a B we have a GOP so we must return the right
part of the disjunction so we have to return right of G of nd now
clearly we have to combine somehow a with G and B and the way to get
G of a B is to use it on G because that\textsf{'}s the only thing we have that
seems to be the right way but then we need to lift a into the function
G and we have this and this is actually according to the identity
law in the function G which should hold this is equivalent to just
F mapping or mapping over G over G B of a function that takes B and
returns a pair in D so let\textsf{'}s just write it like this because it\textsf{'}s
easier to understand what\textsf{'}s happening so similarly if we have a right
on the Left we must return the right of this combination where we
lift the B into the function G and then zip together with G finally
if we have both on the right then we just zip them together and they
remain on the right so you see only when both of the data values are
in the left part of the disjunction only then we can return the left
in other cases we must return it so that\textsf{'}s how it must be now in my
intuition it will be already suspicious if we wanted to return right
in all four cases it means that somehow we are losing information
never returning a left and that\textsf{'}s going to lose information and certainly
that could be an obstacle to satisfying the laws we'll see that indeed
that is so let\textsf{'}s check associativity not verify so objectivity we
could have just written F a zip FB zip FC and substitute with this
code but that would be very cumbersome because there will be 8 cases
to consider it will be a lot of writing in the work let\textsf{'}s instead
try to visualize how this operation zip works in this function and
the way to verify associativity easier is to consider zip of three
values like this with DIF different parentheses first in this way
down in that way but try to define zip in such a way that it is manifestly
independent of the way that you put parentheses so try to reformulate
how the zip is defined so that we can somehow define this operation
directly for three elements rather than defining it only for two if
we are able to define a zip operation directly for three elements
like this in a way that is clearly independent of where the parentheses
are in that a B and C all enter in the same way in this computation
lady there isn't any precedence is not that a and B are first and
then you see somehow then it will be manifestly associative so let\textsf{'}s
see how that works in this case so consider this this situation now
we could have all of them on the left and then we would be in this
situation or return the left after the first pair and also after the
second zip or in the other word will be exactly the same so if all
of them are on the left then it\textsf{'}s just going to be the result is just
going to be to this triple with parentheses here or with parentheses
here but that\textsf{'}s equivalent according to our definition of equivalence
and so that\textsf{'}s associative so if they are all on the left then this
operation is associative the result is manifestly associative now
if even just one of them is on the right then we know that the full
result is always going to be on the right and we know that what what
will happen is that all the parts that are on the left and maybe for
example this is on the left but this is on the right and this is again
on the left all of those that are on the left are going to be lifted
into the front of G using the pure operation and so basically you
could imagine that first we lift all of these that are on the left
into the pure into the G factor and then we have all of them from
the right as if and then we just sit them together so the result would
be as if in the G factor of three values from the G factor and that\textsf{'}s
associative so therefore we have formulated a computation in a way
that is manifestly associative it\textsf{'}s independent of the order of parentheses
and so in this way we figure out that it\textsf{'}s associative it\textsf{'}s much faster
to write out this code let\textsf{'}s check the identity law so the wrapped
unit is on the Left it\textsf{'}s the unit when the left part of the disjunction
which I denote like this in my short notation consider the right identity
law for example so we have some fa which is this type we zip it with
this now if a face on the left then the result will be according to
our definition this which is going to be this left of a and the unit
and that\textsf{'}s equivalent to left away according to our convention because
we can always add or remove units from the tuple and so then the result
is this which is equivalent to that so that\textsf{'}s an identity identity
law if a face on the right you need to lift this into the right and
then zip with FA when we lift unit into G using pure the result is
the wrapped unit which is pure of unit that\textsf{'}s the definition of what
wrapped unities so in relation to the pyramid and so we have the zip
equal to this right of this with a wrapped unit of G now the identity
law for G tells us that this is equivalent to G a therefore the result
is equivalent to right of G which is exactly FA so in other words
zipping FA with this always give you gives you something equivalent
to FA and that\textsf{'}s the identity law and clearly in the same way we check
their left identity if we define the wrapped unit like this instead
then we can see that the identity law will be broken here\textsf{'}s why consider
the zip of a left value with this wrapped unit defined as the right
of wrap unit of G according to our code whenever something is on the
right the result is on the right so the result of this is going to
be right of something now whatever we compute in here we couldn't
possibly or produce a left of anything because it\textsf{'}s already on the
right so it cannot be equal to the left of a our equivalence rules
are that we can rearrange tuples and we can add or remove units unit
values from tuples our equivalence rules do not allow us to interchange
anything else or to change at all anything else so we could not change
left into right and so that\textsf{'}s not going to be covered and similarly
here if we define this to be right then zipping left with anything
could never give a left and so the identity law that would have no
chance and so in this way we see that this implementation is the only
one that respects the laws there are several implementations that
are of the right type signatures but only one implementation respects
the laws so that\textsf{'}s an interesting situation which happens for this
construction now the next construction is the Freeman and over a function
G so G here is an arbitrary contract and this is a recursive type
that\textsf{'}s defined language now we have seen in the previous chapter that
this is a monad and anyone odd is an applicative as well we can define
zip function for a monad like this and we can define pure will not
already has peer and we can define the wrapped unit as pure of one
pure unit so if we have a moon at construction then we already have
the Monad laws the implicative laws are consequences of the Monad
laws when the zip and the pure are defined like this through flat
map so we don't actually need to check any laws here for this construction
because we already checked the Monad laws and the applicable laws
or a consequence when when we defined implicative instances through
melodic instances and the same codes for this construction this construction
was also a monadic construction so we don't need to consider it separately
in this chapter notice that we did have to provide proofs for these
constructions because even though we had anodic constructions of the
same form those required for instance G and H both to be monads now
we don't require this we only require them to be applicatives similarly
here we only require this to be applicative so we have relaxed recall
some requirements as compared with the constructions in the monad
and so since applicatives are a strict superset of monads and we have
relaxed those requirements we have to provide a proof for these constructions
and does not assume units from the user just assume duplicative and
that\textsf{'}s what we have done we provided proofs of the implicit of laws
but only assumed that G and H satisfy applicative laws we did not
assume that G H permanent now in these two constructions there aren't
any constraints on G and H that we changed these are exactly the same
constructions with exactly the same conditions from G H was in the
Monod constructions and therefore we don't need to prove anything
you know they are exactly the same these constructions are stronger
than we need they prove that these are mu nuts and it follows that
these are also ticket ifs but that\textsf{'}s okay that they are stronger and
they prove more than we need in this chapter but that\textsf{'}s fine now the
takeaway is that these constructions also work for negatives because
they are monadic constructions now here are some constructions that
do not correspond to any mimetic constructions these are the last
three the construction six is the constant factor giving a monoid
value so it\textsf{'}s a type Z some type that we know is the 108 it is not
a unit actually we will see this shortly so the type constructor is
defined like this and we don't want to define it as a type F because
we want to keep this Z as a parameter so we again use the kind projector
and we write this kind of type constructor for the type function that
takes type parameter a and returns the type Z independent of a that\textsf{'}s
okay quite fine so as usual first we define the function instance
the functor instance is standard there\textsf{'}s just one remark that I'd
like to make here which is that this function f is not used in the
map function so the map function is supposed to take a value of type
F of a and return a value of type F of B but both F of a and F of
B are just the type Z they don't depend on a and B so we just take
this Z and we need to return a zero we return the same thing it can't
do much else reasonably and we can't use F because we don't have any
age to apply F to and also we don't have any other thing that would
apply to F or any function that would consume this type we don't have
any of them so there\textsf{'}s no way what we could use F in the code of map
so we're losing information but that\textsf{'}s okay so we're losing this F
that\textsf{'}s fine let\textsf{'}s look up the implicative instance the wrapped unit
is monoid empty value this seems to be reasonable what what else can
we return an iterator in a value of type Z but we don't have any data
to compute that so the only value we can return is the empty value
of the monoid and the zip operation is just a monoid combination mono
in operation on a fan of B and we could have defined it in the opposite
order and I will still be valid so this is somewhat this was an arbitrary
choice really so why do the laws hold for this it is because if you
look at the applicative laws formulated like this they look exactly
like monoid laws except that in the applicative laws all of these
are values with type parameters so this is some F of a is a summary
of B the system F of C however if F is the constant factor then all
of these are just the same type Z and then this becomes exactly 1
2 1 1 oide follows there aren't any more type transformations here
they're just this becomes equality and this B\textsf{'}s 3 laws become exactly
the monoid lost so therefore this operation instead of zip exactly
satisfies all the laws and if we interchange B and a it would be exactly
the same laws with being they interchanged where appropriate so this
would be exactly equivalent let us see why this type constructor cannot
be imminent so we could define the pure function by again returning
1 with empty there is nothing else we can return because we can't
reuse use a value of type a to compute a monoid value of type Z so
we could implement pure like this it could implement flatmap by again
returning this F a unmodified now we can't use F at all just like
we couldn't use it in the map so we are losing information in this
function we could also return here an empty value of the monoid or
we could return this value but in any case we would have to lose information
about the function f now the left identity law for a monad is this
which is a flat map with F which is applied to pure should be F but
flat map loses all information about F as we have just seen so this
can't possibly recover F whatever you compute here however you define
here it cannot possibly recover F from a function that ignores its
argument F and so this law could not possibly hold and it could not
hold however you define this you could define it in this way or you
could define it as Z dot empty but still you could not recover F and
this law would not hold so the only constant functor that is a monad
is this factor is the unit because then you're losing information
but there is no information to lose there is only the unit value there
is nothing else that you could possibly return and so you aren't actually
losing any information because there wasn't any information to lose
to begin with so for this reason this is a construction that does
not correspond to an another construction next construction also doesn't
it\textsf{'}s similar to this one except we're having here instead of the pain
we have demantoid Zee now G must be a positive just like here so why
is this construction not magnetic because even if you take for G the
same first factor for example this one the constant constant function
then we will have Z plus 1 which is a monoid but not a moaner as we
just have seen the only constant factor that is one note as a monad
is this the unit so this is going to be not a unit it\textsf{'}s going to be
Z plus unit and so it it\textsf{'}s not going to be Amana so it is impossible
to have a construction like this for a unit where even if we require
that G is a monad still this is not going to be imminent for all G
let'em units let\textsf{'}s see how this construction works for applicative
families so first we define the function instance which is standard
we just apply function f to a under G using the map or if we're in
the left we don't apply it it\textsf{'}s the Z value remains unchanged so that\textsf{'}s
the standard implementation of the functor instance so let\textsf{'}s now look
at the construction so again I have put here perhaps constraint that
I don't need now we need to define the wrapped unit which is of this
type and we have again just like in the other construction we have
two possibilities we could return the left of the empty mandroid value
like this or we could return the right of the wrapped unit of G so
it turns out in this case that the correct way is to return the right
and the left of not know where the empty breaks that the identity
laws will see one define the zip again we need to on the four cases
in the left we just use the monoidal pressure to add together two
values of demantoid now let\textsf{'}s look at what happens when we have the
cross term so a Z on FA is on the left as a Z but FD is on the right
now we have a value of type G of B and we have a value of times Z
we're supposed to return this I'm supposed to return either of Z and
gob can we return this no because we don't have an A we have a Z and
we return and we have G of B we can't possibly get an A from anywhere
so we can't possibly return G of a B therefore we must return left
and the left has only seen so you must return left of this of this
Z and we must ignore whatever was on the right similarly in the other
kids and only when both are on the right then we can zip them together
using the zip in the G factor so in this case it seems we don't have
much choice but how to implement zip we still have a choice about
implementing rap unit let\textsf{'}s check the laws and see how that works
so again we will just do a consideration that zips together with three
values and formulates a result in a way that is manifestly associated
so consider these values if at least some of these three are on the
left then according to our code result is going to be on the left
and we're going to ignore everything that\textsf{'}s on the right so therefore
we will obtain a result which is going to be a monoidal operation
home all of the Z\textsf{'}s that are on the left ignoring everything that\textsf{'}s
on the right we could have three things - Z\textsf{'}s or ones but that\textsf{'}s all
so that\textsf{'}s obviously associative because it doesn't depend on the order
of parentheses and because Z is amyloid and so this operation is associative
in the monoid now the other case is that we have all of these three
on the right in that case the result is the right of zipping of these
three which is associative because by assumption zip is associative
in the function G so we have reformulated as computation in a way
that is manifestly associative the wrapped unit we need to make a
short computation here so for example we have this zipping it with
that if this is on the left result is again the left which is exactly
the same and so that\textsf{'}s identity law if we have G a on the right and
we're dipping it with this then we're zipping this ga with the wrapped
unit which is equivalent to GA by assumption since the identity law
holds for G so we have again right of GA which is equivalent to writing
G in both cases they identity law holds and the same way we check
the left identity law now if we define the wrapped unit as a left
side of the disjunction when we consider zipping of left and right
and the result must be on the left because anything that has at least
one of them on the left it turns the left and therefore it cannot
possibly be equivalent to the right of GE because whatever you compute
is going to be left of something and it\textsf{'}s not going to be right of
G so that breaks the identity law so in this way we find that this
is the only correct definition for the wrapped in it finally look
at the construction 8 is functor composition when G and H are both
applicative factors when their composition is which is G of H of a
is again an applicative factor now this is not a monadic construction
because composition of two Moniz is not necessarily Amanat it may
be or may not be in some cases so it is not guaranteed whereas with
applicatives it is guaranteed I will see an example explicitly in
this tutorial where you have a composition of monads and the composition
is not alone odd but you couldn't get such an example for applicatives
let\textsf{'}s see how that works so we have two factors we define their composition
which is defined like this as a type function and then we define the
map which is standard we just map over H under G so we have a smashed-up
map now let\textsf{'}s define the zip so how do we define a zip we need to
define a transformation like this we need to define also the wrapped
unit so the only way to define the wrapped unit is to do first take
the wrapped unit of H and then lift it into G by using the pure from
G that\textsf{'}s the only way we can get a value of this type the definition
of zip is straightforward we first zip the two genes together using
the zip energy factor the result is a G of the product H a and H B
and then we map under the function f function G we map H a and H B
into H of a times B which is this function which uses the zip in the
edge let\textsf{'}s check the laws for this so I simplified and so let\textsf{'}s check
the associativity the definition is like this like I'm just going
to rewrite it a little shorter because it\textsf{'}s easier to reason about
when when notation is shorter once we have the zip we map that with
essentially zip in the age factor and when we have three values JH
h HB HC when we accept them like this then this is the result now
in order to simplify this use natural tea loafers if the naturality
law says that for this zip if one of these argument one of its arguments
has a map working on it we could put this map over here and work on
the first type inside the zip leaving the second type unchanged that\textsf{'}s
that\textsf{'}s a natural allottee law let\textsf{'}s remind ourselves of the naturality
law that is here if we have a zip that on which some function works
on the argument then we could pull this out we have a zip of those
things without anything acting on it but we can act on the result
of zip by the product of functions so that\textsf{'}s maybe it\textsf{'}s a little easier
to see here so zip yes so zip on which some functions have worked
is equivalent to zip followed by some map so we will do that and we
will pull this outside so how do we put it outside well the result
is that we we still have this back here but before that we have this
map of zip H which takes the first tool it\textsf{'}s a product of two functions
one the zip age and the other is identity so this isn't changed and
zip age is now acting on these two because it was acting on these
two so I'm just using the shorthand but me and it\textsf{'}s kind of it it\textsf{'}s
the same as map of case image being so this map of the page here it
was like this but now we need to apply this to the result of zip which
is going to be of type G of H of M be sr g of h a times H B and H
so then HC needs to be outside of this tuple so that is the result
now we can combine these two maps together using the function composition
law just take this we first compute this and we match on that with
this case and we have this result now obviously this is a associative
combination for zip age where we quickly could commit in parentheses
and so when we do the same computation for this expression we get
a similar function with parentheses in the other place and if we compare
these two we see that these are equivalent because the G factor satisfies
associativity and these are equivalent because that each function
satisfies associative ET and these are just equivalent by definition
and so we have found that the equivalence holds the identity law is
satisfied as well for the in the same way we do a zip with map we
use the identity law for zip in the g-factor first identity law says
that this is equal to gh a dot map of this function and then we just
add zip H on top now this becomes the zip H of wrapped unit H which
is equivalent to H a so this becomes H a to H it becomes identity
function so mapping with identity function does not change the result
so therefore zipping gh a with wrapped unit is equivalent to G eg
similarly we can check the right identity laws so these are the constructions
that I was able to find that build new applicative factors out of
old ones now I would like to give another example of an applicative
factor that disagrees with its own net so what what does it mean exactly
well this is typically a situation when you have a function that has
a moon an instance and also it has an applicative instance and sometimes
you would like the implicit of instance to do something different
than what what a moon adds definition would do we have seen this in
the first part of the tutorial where you would have either moment
which stops up first error but you can define an applicative on either
that accumulates all errors so this is an example of a positive that
disagrees with its moment it\textsf{'}s often the case that you want will not
to agree with applicative but sometimes we want them conditionally
and here\textsf{'}s an interesting example of type constructor where it is
easy to see that it\textsf{'}s really reasonable for them to disagree this
type constructor is basically a lazy list so I will explain what that
means if you delete this function from unit to that and you would
have a definition of the list it\textsf{'}s a recursive definition of the list
factor adding this function arrow means that elements of the list
are not yet computed necessarily you could compute them by calling
this function you can always call it it doesn't require any extra
date and just a unit value which you always have so you can always
call this function and get the next element and the tail of the list
on which you can again call this function get again next elements
and maybe some computations could be encoded in this way where maybe
it\textsf{'}s expensive to compute these elements and this is only done when
you want them so in this in this sense it\textsf{'}s a lazy list it does not
have all its elements already evaluated it\textsf{'}s waiting until you need
them when you need them you call this function and you get your next
element so let\textsf{'}s see how we define this is a list as application factor
this is the short type notation that we have just seen and since this
is a recursive type we cannot use the kind projecting we have to use
a class also cannot use a type alias we have to use a class can you
find it in Scala so let\textsf{'}s do that and I'm just using a very direct
encoding of this like so it\textsf{'}s either unit or a function from unit
to this now in Scala this syntax does not actually mean a function
with unit argument it\textsf{'}s a function with no arguments with an empty
list of arguments Scala has this syntax it doesn't really change anything
for us just a little less typing if we wanted to have a function with
unit argument it would be like this just more typing for no game in
particular let\textsf{'}s define some utility functions so that we can easily
work with data of this type first what\textsf{'}s doing empty list which is
just returning this first unit which is left of unit let\textsf{'}s define
a function that takes an ordinary list and creates this lazy list
it would be useful for testing the idea is that we would create F
with a right which would have a function that will return a tuple
of the first element and the rest the rest will be again F of right
and the gamma function will be the second element and so on and finally
would be an empty list so that\textsf{'}s easily done we match on the list
if it\textsf{'}s empty we return the empty which will you find here if it\textsf{'}s
not empty we match on head and tail will return a F with a right inside
and the function like this which will return a tuple of head and again
a value of type F of a which is the result of applying the same function
list to the tail of the list so that is easily tested now we can create
value like this and in order to get anything out of those lazy lists
we need to actually call the function so this fetches all those things
and calls the function and the result is that you have a tuple with
one element which was a and the rest which is again the same story
again you have to do this in order to get anything out of it so let\textsf{'}s
for convenience convert to ordinary list so that\textsf{'}s how we convert
straightforward function I would call and then call itself again so
these functions are not tail recursive just using it for tests right
now so these tests check that we need these lists work first you find
a factory instance let us straight forward because it\textsf{'}s just a function
so we need to create a new function where we replace arguments and
do a map recursively and let\textsf{'}s create with zip instance and applicative
instance and that\textsf{'}s where the interesting things happen so the first
question is what is the wrapped unit no we could in principle return
a left or we could return a right because they're the type has an
either so we could return the left or we could return the right we
return the left and it will be just an empty list so the wrapped unit
would be an empty list of type unit if we return a right then we could
return a function that has this a which is a unit and then again returns
the same wrapped unit that\textsf{'}s what we do in fact it\textsf{'}s a recursive definition
that in effect it is equivalent to a never-ending sequence of unit
values in the list because the list is lazy it doesn't actually evaluate
infinitely many elements but if you request the next element if you
evaluate this function and you would get again the same function that
would generate the rest of the list so the rest of the list is exactly
the same as the list itself and so in other words it\textsf{'}s a never-ending
sequence it\textsf{'}s not actually an infinite sequence in memory of course
it\textsf{'}s conceptually equivalent to the infinite sequence because you
can request next elements as many times as you want you will still
have always next elements that I found the same elements which is
empty so converting this to list would be a stack overflow or memory
over out of memory error fix the Stack Overflow first now zip operation
is interesting but it\textsf{'}s really trivial in a sense because if one of
them is empty will return empty and if we have two functions so GA
and GB are functions of this type and we again return a function which
just has the tuple of the two first elements and then zip in the rest
recursively so this is a typical implementation of a zip of two lists
except that we need to dance around with these function calls we have
these functions and we need to match in a different way and and so
on but other world other than that it\textsf{'}s the same and so zipping a
list of two elements with a list of three elements cuts this list
of three elements to length two it gives you this as a result so this
is a standard behavior of the zip method on lists but also this wrapped
unit acts as a unit if you zip it with some list the result is the
same as the initial list after the equivalence transformation so how
does it work well since the wrapped unit logically represents and
never-ending Western unterminated sequence in this list is finite
the zip function will cut the longer sequence because that\textsf{'}s the code
if one of them is is on the Left which is an empty list then the result
is an empty list so whenever get an empty list we cut and so that\textsf{'}s
going to be the result indeed zip defined in this way I can't do much
more than cut because if it didn't cut we would have to produce here
another element of type string unit but there\textsf{'}s no string to get to
right here logically you would have to cut certainly in some applications
this is not what you wanted but in many applications that\textsf{'}s what you
want you to cut the laundry list and you could conceivably you could
do other things but what if the first list is empty when do you didn't
there aren't any values for you to fill you have to cut and sew however
if you use the list monad the definition of pure is not the same it
is not an infinite sequence it is a sequence of length one so the
pure would be just this be in one element list and the standard zip
function zipping with this would certainly not do what you what you
want it would cut at length one now certainly if you define zip through
the munna instance and not in this way and you would have a very different
behavior then of course the laws will hold just zip defined from the
monad will take each element from the first list and each element
from the second list and put all those pairs as a result in waste
so for example zip of waste and one to waste of 1020 it would be a
list of 1/10 1:22 10 to 20 so certainly this is very far from the
standard function zip on lists it could be reasonable for some applications
but the standard zip function doesn't do this it does that and therefore
for the standard zip function the correct wrapped unit is this infinite
sequence P not this and so this is an example where the standard zip
function which suggests an applicative disagrees with the mu naught
which is also standard for the standard flat map and disagrees with
that and so that\textsf{'}s but but actually they're both useful in different
contexts so this is exactly the kind of example I was talking about
and the reason that this disagreement might be troublesome is that
if you defined for example code that has a for yield construction
when you might be able to simplify it using zip what if you notice
that you have this kind of construction and you say all that this
is obviously a map - this is a map - or this is a zip like this zip
and this would be a map - and then you will be tempted to refactor
this code by doing something like this but if the zip implementation
disagrees with the Munna instance then you would have changed the
functionality you cannot replace this code with this code unless the
applicative instance defines map to in the way that is exactly the
same as what would follow from flat Mac now if you are using a type
constructor for which the model instance and the implicative instance
disagree then you should never refactor code like this but you might
be tempted to or you might just do it without thinking it\textsf{'}s very confusing
but these things are not the same and so it is recommended therefore
to avoid these situations are not to define applicative instances
that disagree with model instances if you need that the easiest way
out is to rename then a type constructor to some other rename have
an alias or some different type would only have the implicative instance
but not a model instance and the first type would be a monad and you
would only use the first type when we when you use as a monad in the
second when you use as applicative so but in this way you avoid potential
for bugs that would come out of this kind of confusion so finally
let\textsf{'}s look at some examples of non applicative factors so these are
the examples now the first example is the disjunction of two reader
mode ads essentially so reader mode on of course is applicative also
it is this construction but their disjunction is in general not implicative
another example of not duplicative is this this is a functor in a
because a is here in a covariant position so this is to the left of
the function arrow so this entire group is contravariant in the controller
in position but inside it a is also in a contravariant position so
that cancels out and the result a is covariant here similarly here
is covariant and also a is here covariant to the right of the function
error so these are functors but they're not applicative let\textsf{'}s see
how we can verify that so i defined these type constructors i also
defined this G which is I've just reversed these two errors the result
is that it\textsf{'}s a contra factor it\textsf{'}s not a fuck function anymore but
it\textsf{'}s very similar in structure so now these are our three examples
F H and Kane I'm going to try to implement the zip function using
the curry Harvard library so I'm going to ask a Craig Howard library
to implement any code that has this type signature and this is the
Olav type method so I'm going to find all of these so that the result
is going to be a sequence of implementations and then I'm going to
look at those sequences so this is all happening at compile time and
so these tests run now the length of zip F is 1 which means that there
is one implementation of this function which is this type but when
we look at the code which is printed in a short notation we see that
the code is that as function returns always none so it always returns
an empty option a zip function that always return an empty option
is obviously going to violate laws as for instance identity laws well
it won't violate a social Timothy because always returns the same
thing but it\textsf{'}s going to violate identity laws that require it to preserve
information and since the identity laws say that zip of something
with the ident with the wrapped unit must not change the something
so it should not lose any information if zip losses information then
it\textsf{'}s certainly going to violate the identity walls and so the only
implementation we have of this type signature which is the zip type
signature from this funding is going to violate identity laws so there
is no good implementation and for these other factors there\textsf{'}s not
a single implementation at all of this type so those types could not
be instantiated could not be implemented by any code so there\textsf{'}s no
code that\textsf{'}s generic and all these parameters that implements this
type signature and also this type signature but for the G there are
actually two implementations G\textsf{'}s a country factor I just took this
and I reverse the arrows and it turns out there are two implementations
so that\textsf{'}s interesting and so let\textsf{'}s look at contra factors now all
a blicket of puncture laws that are formulated via unzip and wrapped
unit actually don't use the map function so we can formulate the same
laws for contra factors so we can say an applicative contra factor
is a contra function that has a zip and wrapped unit methods with
the same type signature and the same laws identity laws law and social
dignity law so that\textsf{'}s the definition so we will look at constructions
shortly but one thing we need to keep in mind as a contra funders
are different from functions and that they don't have map they have
contour map so for instance you cannot take a wrapped unit and map
it to get a pure out and because you don't have a map you have a contra
map and so it slightly it\textsf{'}s slightly different another thing is that
we always have a function like this just drop B and take the first
element out of a tuple if you control map with this function of CA
then you get C of a B because that goes and you're in the opposite
direction CA with this function goes from here to here and to see
a B which looks like what you want to implement the zip you take the
CA you just contra map it and you get c but that\textsf{'}s invalid as an implementation
of zip because it loses information about CB and we know that would
violate the left identity law if you put identity here you should
reproduce CB on the right hand side but you lost all information about
it so naturally T must hold but with contra mapping set of map so
that\textsf{'}s another difference now if you try to control map this with
a function from one to a you can't it\textsf{'}s the wrong direction you can
confirm map it with a function from a to 1 and you get C away for
any a so that but that\textsf{'}s kind of that\textsf{'}s different from pure but it
can be seen as an analog pure has a type signature a going to F a
this does not have a going to anything you don't well you could imagine
that you have it but you don't use that information so you don't use
any values of type a to create this already can't read them so that\textsf{'}s
yet another difference and also there is no contra app there is cerebral
mind there is no analog of app for control factors so these are the
these are the control factors and indeed we'll see this is one of
the constructions that the disjunction of to a positive control factor
is again a pretty check this is this is this construction which we
will look at shortly so all right so now we verified using the curry
Howard library the these factors are not applicable by trying to implement
the type signature of zip and finding in this way that for this factor
there is one implementation of this type signature but it loses information
and so it could not possibly satisfy laws and for these two types
we found that there aren't any implementations at all for the type
signature of zip now I should comment here that actually is quite
difficult to prove that there are no implementations of zip it\textsf{'}s actually
quite difficult to prove so I'm using the very hard library that performs
exhaustive search of possible implementations but certainly it\textsf{'}s not
really a proof I'm just running some code maybe it has bugs so it\textsf{'}s
hard to actually produce a good proof and I'm not going to do it it\textsf{'}s
it\textsf{'}s if you if you go back to the Carey Hubbard correspondence tutorial
you will see but this is equivalent to finding a proof in the constructive
logic or or showing that there is no proof so there are methods for
showing that there is no proof proof theory gives you tools for doing
this but it is difficult and cumbersome and so that\textsf{'}s why I'm using
the curry covered library in which I have a certain degree of confidence
where I can just ask it how many implementations and given type signature
hands so having finished with constructions we notice that some of
them contain one nodes so you know it\textsf{'}s seem to play an important
role they are very similar to applicative function in some interesting
ways so let\textsf{'}s actually ask what are more node types so what are the
types that I could use here in this construction the answer is surprisingly
in Scala any type ism or not all non parametrized exponential polynomial
types are mono it\textsf{'}s what does it mean we have mono at constructions
and in the previous chapter and I could have made this observation
already in the previous chapter that these three constructions give
new monoids out of previous ones and also that all the primitive types
integers floating points and so on sequences and strings unit all
of these types have at least one way in which they can be implemented
as monoids instances of the monomial typeclass for instance these
are all like numbers they can be added together and that\textsf{'}s a fundamental
operation these are all like sets where you can have an union of two
sets so here is a sequence and union is just concatenation and this
is a set Union and this is a map merging Union but basically they
are set like their MA nodes and strings can be concatenated because
they are grooving to sequence of integers and unit is a trivial annoyed
and case classes you can define using these constructions and function
types you can define using this construction so a function from say
float to a sequence of strings it\textsf{'}s just one of these constructions
applied to one of these types and so they're monoids so all exponential
polynomial types that is all types constructed from these three operations
starting from the primitive types are going to be always one with
at least in one way sometimes in more than one way so here\textsf{'}s an example
consider this type expression in Scala code this would be implemented
as a sealed trait with three case classes because there are three
parts of the disjunction this is a monoid I don't have to worry about
how to implement it because I have these constructions and once I
decompose this into some of these constructions starting from primitive
types I can just generate the monorail instance automatically or mechanically
notice that this does not have any type parameters if I have type
parameters then I don't know if that type is a monoid I don't know
how to implement and the moment instance for it maybe it will be able
know it when this type expression is actually used in my code but
I don't know that so I don't know how to implement and here\textsf{'}s an example
of an envelope type with type parameters so if this were a to a that
would be already a monoid it\textsf{'}s a function one weight with function
composition but here I cannot compose two functions of type A to B
and get a third function again of type A to B no way I don't know
how to combine A\textsf{'}s I don't know how to combine B\textsf{'}s there are unknown
types if I knew that they were more nodes but at least be if I knew
that B is I don't know that\textsf{'}s enough already I have this construction
but I don't know that I don't know how to combine so that\textsf{'}s that is
to say all types that don't have type parameters and our exponential
formula such as this one they're all Minuit\textsf{'}s so it is in this sense
that I say all non traumatised exponential trinomial types and paranoids
very interesting conclusion follows from it namely that constructions
one two six and seven give us a way of expressing all polynomial factors
with monoidal coefficients as applicative factors starting from one
nodes we can build applicative instance for any polynomial factor
so how to do that the short summary of this of this construction is
that we need to rewrite the polynomial in this form which we always
can do isomorphic Li we can transform the type into this form just
like in school algebra this form is called Horner\textsf{'}s scheme for polynomials
so a is the argument and these are coefficients in school algebra
that would be numbers constants and this is the variable in the polynomial
and so because we can write it like this these are just a sequence
of constructions that you apply and you get an applicative function
so let\textsf{'}s see how that works suppose you have a polynomial factor and
which you can write in a short type notation like this you have some
coefficient that is constant type could be complicated but it\textsf{'}s constantly
you know it could be like this but it does not have type parameters
it\textsf{'}s a constant type multiplied by some number of A\textsf{'}s or some power
of a but a fixed number and another monoidal coefficient so we assume
they're all one which is Z and Y because they are of this kind so
they do not have type parameters we can start with the highest power
of the polynomial like we do in school algebra and then some smaller
power and then finally we go down to power one and zero with some
constant types here so this is one way of writing a polynomial which
we can always do another way would be then to put parentheses in like
this so starting from the lowest power we take a out of parentheses
and then in fact factor it out the result is a polynomial of lower
power which we can write again factor out in the same way and finally
in the middle of it there will be some last a and Z Z is the coefficient
and the highest power of the point number so we can always transform
the polynomial into this into this shape into corner scheme and notice
here some steps could contain more than one a so for example it could
be like this because some coefficients could be zero conceptually
speaking or zero type as also something we could use here for generality
but we don't have to each of these steps corresponds to construction
7 which is this Z plus some G of a actually I think it was called
and construction 2 which is multiplying a and G of a where G is already
negative and a Z can be then used like this they can add Z and or
you can multiply by a and that\textsf{'}s still applicative these are the constructions
construction 2 and construction 7 so indeed we can find that it is
a picketing but how does the implicative instance actually operate
so what does the applicative method wrapped unit for example do or
zip what do they do two types like this how can we how can we visualize
those things so here\textsf{'}s how the wrapped unit for construction 7 is
this we have found and wrapped unit for construction - is this and
so the wrapped unit for the entire polynomial is going to be every
time you step through construction 7 you discard the Z so you you
go to the right like this in other words every time in construction
7 when you go you discard this then you keep a discard this you keep
any discard that keep any discard that keep a and finally you're here
so you have discarded everything but Z eh eh eh in other words everything
but the term of the highest power of the polynomial so therefore the
wrapped unit for FFA is of this form is the highest power term the
polynomial where you take instead of Z the unit value or empty value
of the monoi oil and instead of a you put the unit values so that
is going to be the wrapped unit let\textsf{'}s look at how zip is defined so
it would be good if we visualize for example zip of these two terms
then if we can do it then since zip is distributive one zip of this
and some other polynomial essentially is just one zip of this train
because a value of this type must be in one of the parts of the disjunction
so it\textsf{'}s one of these either this or maybe it\textsf{'}s this so it\textsf{'}s sufficient
to be able to compute zip for two monomials like this so let\textsf{'}s see
so construction seven says that the result of these is of type RA
a because construction seven says if one of them was on the Left we
discard what is on the right in other words if we are here for example
we discard this so if two polynomials are zipped together we discard
the one that has higher power so we discard this as discard the power
so we discard the coefficient at the higher power and the result is
the coefficient of the lower power that that remains and we need to
discard so we will go through these and we will discard as many of
these B\textsf{'}s as we need to in order to have a pair for each a so in other
words we'll discard B 3 and before here and we'll keep B 1 B 2 actually
it might be that we discard B 1 B 2 and we keep B 3 before that could
be an equivalent equivalent definition doesn't matter right now we
just want to understand the principle so the principle is first of
all we choose the polynomial of the lower of the two powers we discard
the monoidal value of the other one and we discard the extra values
that cannot be paired up with ours because we need to zip those together
and we return this so we treat them as lists we zip them together
as lists so we cut the longer list when we do that and we discard
a coefficient at the longer list also keep a coefficient and the shortened
list if the two lists are the same length we don't discard them as
we use the monoidal operation from the coefficients and we just zip
the lists as before so in this way we can visualize how constructions
2 and 7 as well as constructions 1 and 6 as far as I remember correctly
yes as we need a constant factor sometimes we need the entity factor
sometimes and we need these two constructions so in this way we have
defined how they work through constructions and we have visualized
how they actually work on specific terms of these types so that certainly
is plausible that you could take any polynomial factor and more or
less mechanically transform it into this way into this form check
that all the coefficients are monoids and then generate noise the
Romero instance for each of them and then generate the applicative
instance for effect here are examples of polynomial factors but are
applicative because they are point omean so the first example is interesting
because this type constructor cannot be defined as a walnut cannot
have a model instance you can define the methods pure and flatmap
with the right type signatures but they will not satisfy the laws
there would not be associative 'ti and identity laws for an unsatisfied
no matter how you try people several people have verified this by
explicit calculations but it is applicative so the implicit of instance
is very easy and just this construction of adding Z to an applicative
factor which is a product of two identity and factors so obviously
this is an applicative factor also it\textsf{'}s interesting to look at this
as a composition of two functions one option so one plus something
is option and then a factor which is the pair a a so that\textsf{'}s clearly
a polynomial factor so the composition of option option of prae is
not am honored but option by itself is a monad and tear a a by itself
is also a moment so this is an example where composition of two units
is not among that the composition in the opposite order will be imminent
the pair of two models one plus eight times one plus eight that is
a moment but not in not composition in this order and in this example
is just polynomial is just to visualize what I mean by polynomial
with monoidal coefficients it\textsf{'}s like a polynomial but the coefficients
must be unknown so any types that have no parameter a in them so like
the Z that must be a monument now this this is a one that this this
factor I believe is a Mona but it\textsf{'}s not obvious how you need to find
Mona constructions but for example we have here a writer Monette obviously
and then you you have a plus so you multiply identity with the writer
Monat so that is a product construction for bullets and then you add
a that\textsf{'}s a three-pointed construction and that\textsf{'}s also a moment so
through finding a sequence of constructions starting with a writer
mu naught which we know is a minute we can show that this is a moment
without explicitly having to prove the blows hold and notice that
our examples of non applicative factors were all non polynomial so
they all had function in them christmas they're not polynomial factors
indeed there aren't any examples of polynomial but not applicative
factors that have no type parameters and only monoidal coefficient
is very easy to drop in something like this and say all this is not
monoidal and if i have a coefficient like this then obviously I don't
have applicative factors so that\textsf{'}s certainly would be an example so
polynomial factor with non monoidal coefficients that\textsf{'}s very interesting
perhaps but still it\textsf{'}s a valid example so let\textsf{'}s continue and take
a look at Concha funky constructions I already described how Concha
front was are defined so in the next and final portion of part 2 of
chapter 8 I will talk about the applicative control under constructions
as well as Pro factors and applicative profounder constructions 

the first construction is the constant factor where the type Z must
be alone right now this is exactly the same as we just had here against
construction six and in fact construction six was examined and we
have found construction six as follows with we have verified the walls
but we did not actually use the fact that the type constructor was
considered to be a factor so we could have defined exactly the same
code without using this typeclass instance of furniture and in fact
I have defined also typeclasses that I pass control Mujib which is
the same methods except it expects a contra factor instead of factor
but other than that it\textsf{'}s exactly the same type signatures so the result
is that we actually don't need to prove any more than we already have
the previous proof goes exactly the same word for word for a contra
function here as it went for the function because we never used the
fact that we consider this type constructor to be a factor of this
type constructor is of course somewhat trivial it does not depend
on type a but never but this exactly the same logic will apply to
many of our constructions that we just considered four factors for
example the product construction is exactly exactly the same kind
the product construction is defined here for a factor but we actually
don't use a factor instance as a constraint when we define the zip
and the wrapped unit and if we look at the truth or associativity
and identity laws we never use map in any of these proofs we actually
never assumed that G or H are factors we assume that for example equivalences
can be established between these these values but these grow answers
can be established for contra factors equally easily as four factors
so for example for a contra functor if you if you want to compact
if you want to convert for example C of a C into c of a b c like this
this is an equivalence that is required in proven social TV t for
certain functions on constructions what you need is a function that
goes the opposite way from here to here and of course this function
exists it\textsf{'}s a trivial reordering of the tuples or as for functor we
needed a function that went in the other way but also that function
was clearly available so there is not another problem going through
exactly the same proof and just substitute in this kind of equivalence
which is exactly similar whenever we need equivalence between list
of tuples and also the equivalence between a tuple with unit value
and a single value which is necessary for it you know the identity
was the non-trivial construction is this one because there is no analogue
of this construction for applicative functors or for Mullens product
matter as we have just seen in general the disjunction of to placated
factors is not applicable in all cases and this junction of two monads
is not abundant in all cases so let\textsf{'}s look at the implementation of
this construction we use the cats library for contravariant which
is their name for contra factor and we define this type constructors
in either of G\&H assuming that both G and H are contravariant and
this is also controlling it this is how we establish that we define
continuity so contra map should map A to B using a function from B
to a well this goes exactly like in the functor case except we use
Concha maps instead of apps so if we're on the Left we use left and
we map in the G country furniture where on the right we return right
and we map in the H control factor so now we can use applicative instance
and we will use both contravariant and contract lucrative typeclasses
we actually will need that here\textsf{'}s how it goes so the wrapped unit
first needs to be defined so that\textsf{'}s a value of this type now here
we could return the left with wrapped unit of G or we could return
a right with wrapped unit of H and actually this choice is arbitrary
it could return a left or we could return a right we could then define
the zip accordingly and laws would hold the reason this is so is because
this construction is completely symmetric there is no difference between
G and H and so if we are able to define things with this choice and
just by swapping G and H we will be able to define this construction
with the right choice so let\textsf{'}s make this choice arbitrarily so that
we're on the left with wrapped unit so now how do we define a zip
we need to transform this and this into this if we are on the Left
then clearly we just turn the left we have two left G of a and G of
B we can just zip them together using the zip from the G country factor
and if we're in the right if both of them are on the right we can
just zip in the H country factor so that\textsf{'}s clear now what do we do
if one of them is on the left and the other is on the right well we
need to return either left of G or right of age what do we do well
we have now seen two cases when we had a disjunction and we implemented
the zip function for this Junction in each of these two cases what
we had to do is that if the wrapped unit was on the left then the
mixed case needs to be on the right if the wrapped unit wood is on
the right and the mixed case needs to be on the left and that was
kind of the pattern we have seen in the previous two examples so let\textsf{'}s
follow that pattern and we'll see that this actually works so how
do we return the right of H a B now we have only an H of B and we
have also a G of a now we can't possibly combine G and H there\textsf{'}s no
method for that so we have to ignore G and we have to transform H
of B into H of a B but that\textsf{'}s possible H is a control factor so we
can confirm mark it with this function that transforms a B I call
that x and y here but it would be easier negative read the code I
called it a and B are because then the types will be more clear so
I always have this function that transforms a B into B it actually
ignores eight so I can kill that and that function transforming a
B into B contri Maps HB into H of a B and that\textsf{'}s what I need I need
to transform HB into H of a B and so that\textsf{'}s why this code has the
right type and I do the same thing in the other mixed case I return
a right of H a and I contour map it like this so I transform H a into
H of a B so having implemented it let\textsf{'}s check the laws how do we reformulate
it so if we consider this kind of combination if all of them are on
one side so both all three on the right or all three on the left then
we we can do immediately we can see what happens it will be either
on the right of h HB HC whole zip or on the left of GH g BG c all
zipped so that\textsf{'}s clearly associative because we are now doing zip
into in the factor H or an F and Q G and that\textsf{'}s associative by assumption
now if some of these are on the left and others are in the right when
according to our code all the left ones are ignored and all the right
ones are control mapped so that they have the right type and the Contra
mapping is just with the trivial substitution of tuples so clearly
all the right ones are going to be just converted to this using the
trivial konchem up and then zipped together and so the result would
be something like this it will be a contra map with this where what
say C was on the left so it was ignored and a and B were on the right
so they were not ignored and then we we need to zip so that\textsf{'}s associative
because the condition that we are ignoring all the ones on the left
that condition is independent of the order which is no matter what
we add parentheses we put in first around these two or around these
two the condition of dropping all of these that are on the left that\textsf{'}s
associative not independent of the order of parentheses and then we
will come to map it finally into this type unzip them all together
{[}Music{]} that\textsf{'}s associative as well for with the zip ages out of
place here now identity laws are actually checked using a cop as an
explicit computation because you cannot just argue about it a lot
of some symmetry consideration we have to actually compute and verify
that our intuition was right that we we had a left here therefore
we need a right here - let\textsf{'}s check so let\textsf{'}s take some arbitrary FA
and zip it with the wrapped unit which is this and the result is that
we need to match according to this code you can match like this not
only two pieces remain because we have a left here if they're both
on the left we do a zip now this one GB is actually this so that\textsf{'}s
going to be equivalent if it\textsf{'}s on the right then we're actually ignoring
this GB according to our code we need to ignore this and we are on
the right we do a contour map which is like this and this is just
a contour map that is the isomorphism or the equivalents that we allow
so that\textsf{'}s the equivalence expressed by this symbol as I'm using it
and that\textsf{'}s equivalent to right away J cuz contour map with this isomorphism
is precisely the equivalence and so then right away J here we have
right over J here so identity was cold so clearly this would not hold
if we didn't have a right in this in these two places so in this way
we verify this construction now this construction says that for any
factor and applicative contrapuntal G this function is applicative
as contractor let\textsf{'}s see how that works this is the type constructor
so as a type function it\textsf{'}s contravariant because obviously this is
a factor by by assumption H was the front and this is a control factor
so the concha functor is here in a covariant position and functor
is a in a contravariant position so the result is contravariant to
implement that contravariance is easy you return a function which
takes HB now you have to compute some GFP so how do you do that you
can get G of B if you first get G of a and then control map it with
this so how do you get G of a you just substitute into a fey some
HIV but how do you get H of a you take H of B and map it with F because
H is a factor so that\textsf{'}s what we do we map HB with F substitute that
into FA and then confirm map the result with that and this could be
generated automatically for us now let\textsf{'}s implement the zip now we
are using the function instance on H to do that but we're actually
not using a contravariant instance on G for this let\textsf{'}s delete this
we are not using concern up in this code we're using map on H so we
need the function constraint on H but we don't need contraband two-factor
constraint on G for this code the wrapped unit it\textsf{'}s a value of this
type so how do we generate a function of this type role we can take
some H of unit but there\textsf{'}s no way for us to use that H of unit to
make G of unit we already have G of unit anyway it\textsf{'}s the wrapped unit
so let\textsf{'}s ignore the argument and return that wrapped unit how do we
do this so that\textsf{'}s a bit of a complication we have an H of a - G of
a H of B 2 G of B and we need to return this function so let\textsf{'}s return
this function so we return a function that takes HJ b and returns
G a B so how do we get a GLB well clearly we need GA and GB for that
so we need H a and H B so that we can substitute those into F a and
every how do we get h + HP while we take H a B and project out side
B we drop the beat so that\textsf{'}s just a map with this function look drops
the be out of a tuple we could write this function more concisely
like this but anyway so that\textsf{'}s how we do that so now we get H a I
get H beam and we obtain G of a we obtain G of B and we zip them in
the country function G we're done what type is correct what seems
like it was the only possibility to implement these types let\textsf{'}s check
the laws so here it\textsf{'}s hard to reason about these these values in some
hand waving in fashion and and we formulate them explicitly it has
when you firstly applicative I'm sorry manifestly associative it\textsf{'}s
it\textsf{'}s hard let\textsf{'}s write down the code so let\textsf{'}s consider this expression
first so this expression has this type from this to this we write
down those things we just in line just in line hjb map 1 HK be mapped
to I in line them so let\textsf{'}s now zip this with FC so that would be more
complicated we have FA zip FB and then we have apply this function
because this is this 2h a BC map one zip FC h ABC map 2 so if we just
substitute the definition of zip again and we have this expression
now notice we have here H ABC map 1 map to map one map 1 map 1 map
2 and H ABC map to now our H ABC is actually of this type so it has
a nest tuple let\textsf{'}s simplify that let\textsf{'}s map this each ABC as the flat
tuple and convert it into our non flat tuple first so we convert it
and then we would have these expressions which are basically just
taking first element of this tuple which is this then again taking
the first element which is this so this is basically projecting ABC
onto a which is to be equal to that so that simplifies our expression
into into this and then we contra map the result in in this way so
that we know well that that will transform the nested to fall back
into non-listed since it\textsf{'}s a country map so here\textsf{'}s the code that results
from this operation we start from each ABC which is flattened and
then we I just substituted all of this country mapped at the end and
then I have simplified these things so I have F a of this zip FB of
this zip FC of this and so I first have to zipped together and then
a zip it with this FC now the last step is actually zip in the G contractor
because this is zip between values of F of Sun and F is a function
from H to G so this zip is associative and I'm just applying some
kind of a isomorphism which is equivalence don't care about that I
can always apply it whenever necessary and so the main result is that
I have here at this expression that is manifestly associative by assumption
because this is a zip in that country functor G and everything else
is perfectly symmetric so if a HIV seen that one as being HIV seen
up to FC hn be seen up straight so there\textsf{'}s no asymmetry and so I expect
when I start with the other order of parentheses to get exactly the
same thing with different parentheses and so then because of associativity
of G these two are equivalent and these two rows I can always add
or remove whenever necessary so that verifies the associativity law
and let\textsf{'}s look at identity the identity law is that this zip of some
arbitrary FA with this function that we define that always returns
wrapped unit of G ignoring its argument so let\textsf{'}s find out what that
does so the code is like this so we have some H a and H beam that
we define right here and then we do FH a zip F PHP now HB is actually
this but it\textsf{'}s the function FB that is acting on it is this function
that ignores HB so it means actually ignored and result is always
this so the result is going to be fa h a zip this now this is the
zip in the g control function which we assume satisfies the identity
law and therefore this is just mapped into G of a into G of a unit
which is the awesome orphism and so basically we start with function
FA and we have a function that takes H a B maps it into H a and applies
FA to that so that\textsf{'}s basically if you look at how its how its map
its mapped using this isomorphism which is going to be the isomorphism
between a common unit and a that\textsf{'}s our equivalence and so that\textsf{'}s basically
H a B is equivalent to H a and therefore and so FA of H a is the same
as FA of HIV well of the equivalents and so we take FA and we return
a function that takes H a and applies Ephrata HJ so we take a favorite
turn effect so that\textsf{'}s identity so therefore this returns a function
that\textsf{'}s equivalent to FA up to there is some morphisms that we have
such as this one and so the left identity the right identity holds
that we just found and left identity holds in the same way just H
beans to the AJ so so much for this construction now this construction
is a functor G at the contrapunto edge so if we look at the corresponding
construction for functors this one you see we are not using the funk
terminology you're using functor on the edge actually I think that
is a subtype this is a mistake so we use a map on on G G must be a
functor but we are not using map on H so we need to we can delete
this we don't need type constraint constraint that each is a factor
and when we check the laws we use map but always on G so we we take
out these maps but these are values of the function G so we never
use map on H and here also we use a map but only for G you never use
map on any values of H and because of this the proof that we gave
for this construction for functors where G was a functor and H also
a functor now G must remain a funkier because were using map on G
all over the place but it doesn't have to be a frontier it could be
a country functor so this construction is very similar to this one
and the proof goes through exactly the same because we don't actually
need the functor property of H we only need the lucrative property
but not the functor property so we are not using map or country map
on each hello they're only using zip and rapped in the proof will
go through exactly the same word for word so these are the constructions
that I was able to find for country factors now the interesting thing
here is that we have constructions that have constant factor we don't
have identity factor because it\textsf{'}s a con is not a country factor it\textsf{'}s
a factor but we have a constant culture factor we have product disjunction
or some and function or exponentiation so we have exponential polynomial
constructions all of them are here we also have composition but this
is not necessary if we have these three constructions we can come
we can build up an arbitrary exponential polynomial culture factor
with monoidal coefficients as long as we have these all the constant
types that occur must be money or it\textsf{'}s so this is what means to have
constant coefficients for exponential polynomial country factors and
then we have covered all possible country funders so essentially all
exponential trinomial country factors with manorial coefficients have
an applicative instance through these constructions so as long as
we found any exponential polynomial country factor with monoidal coefficients
we know it\textsf{'}s applicative there\textsf{'}s no there\textsf{'}s no question and no counter
examples of non duplicative such country factors so this is very interesting
so we did not have this four factors that all exponential point normal
are factors but that\textsf{'}s the example I have seen so I was trying to
do counter example so this is a counter example four factors this
is not applicable but if you reverse these two arrows you get a contra
function and it\textsf{'}s applicative and that we have seen that it it had
implementations and we know why it\textsf{'}s this construction so the conclusion
is that all the clickety of contra ventures are basically you can
write down are going to be exponential polynomial contra factors and
vice versa all the exponential polynomial contra factors are going
to be negative now let\textsf{'}s talk about true factors in the first part
of this chapter we have seen type constructors that are not functors
but applicative and these were option actually also not control factors
and there are two main examples that we have seen one was the typeclass
from annoyed and the other was the fold the type transfer fold or
rather the type just the data structures were fold we had full diffusion
and the data structures were fold the first variant of it was neither
a function or a contra factor and yet it was applicatives we could
have an negative Combinator for it so those are proof factors informally
speaking pro functors are type constructors that have the type parameter
and the type parameter occurs both in contravariant and covariant
positions because it occurs in both of these positions you cannot
have a map and you cannot have a contra map for this type parameter
here\textsf{'}s an here some examples typically this would be an example so
you have a function from this to this and the type parameter occurs
both in contravariant and covariant positions another example you
have a disjunction or some type sum of a and a function but so here
a is covariant and here is contravariant and so these are typical
Pro factors what would be an example of a non-pro factor no clearly
anything you can write using exponential polynomial operations there\textsf{'}s
going to be a pro factor because the type type parameter is going
to be either on the right or or on the left of the function in room
and the only way to have a non-pro factor is to have a non exponential
polynomial type constructor an example this would be a so-called generalised
generalized algebra data type which I find not a helpful name but
these are basically I would say these are type functions that are
partial partial type functions we have seen that concept in the chapter
on typeclasses these are just partial type functions they are not
defined on all types they're only defined on certain types in in some
specific ways and here\textsf{'}s an example in Scala so you have a trait which
is parameterize by type a but there are only two case classes that
that implement this trait and they have specific type parameters values
here int and unit and so it means you cannot instantiate a value of
type say F of double it\textsf{'}s impossible you can only instantiate F of
int and F of the unit and as a result you also cannot instantiate
F of a for arbitrary a and so there\textsf{'}s no hope for you to have napkins
from the app or anything like that because map and confirm happily
require you to be able to transform F of A to F of B for arbitrary
a and B and you can't even instantiate those F of a and F would be
for arbitrary amb and so no hope for that kind of property for these
types so these are partial type functions no hope for them to satisfy
good properties I'm trying to invent a good notation for these kind
of type functions I'm not sure this is a good notation but this basically
means a string but it is ascribed that this type F event and an int
but it\textsf{'}s considered of type F of unit just by by hand we just say
this is a for unit and this is evident maybe this notation is useful
but in any case at this point I have very little to say about these
partial type functions except that they are not true factors this
is an example of a non-pro factor now notice I have not yet actually
give it even a good definition of a profounder I've Illustrated what
I wanted to achieve these kind of things are pro functors and have
a in a certain position but this is not a good definition because
it depends on being able to write a type in a certain dessert away
and what if we don't know how to write it in a certain way maybe what
if this is actually a profounder just I don't know how to write it
correctly we need a better definition a rigorous definition there\textsf{'}s
a typo I'll fix it a rigorous definition or a profounder which is
that it is a type function with two type parameters such that it is
a contra filter in a and the factor in B so a is contravariant b is
covariant if such a type function exists that PA is defined like this
when we put a and to be the same type then that type function is a
pro factor so for each Pro functor there must be a way to split it
into a function of type function of two type parameters one of them
is strictly called contra variant and the other strictly covariant
and if you can do that then defining P like this then P is a contra
fun it is a pro factor that\textsf{'}s the definition of a pro factor so obviously
we can do this here we can say well this is going to be a and this
is going to be B in the Q so we define Q of a be like this so Q is
1 plus int times a going to be and here we put here be because this
is covariant and here a because this is contra here so that will become
the Q that corresponds to the P so basically the idea of this definition
is that a pro functor is a type function where really you can split
it into a function with two type parameters each purely covariant
or purely contravariant and that\textsf{'}s and then then obviously for the
contravariant you have a conscience where the covariant you have a
layup with the Loess separately holding for a and for me with a usual
laws and since you have that then you can apply something called X
map which is just a combination of map and contra map map in being
in control map in a accepted then after that you said the same type
triangle the result is that in order to map a profounder from one
type to another you need functions from A to B and from B to a going
in both directions if you have that and you use this in the map use
this in the Contra map for Q it\textsf{'}s a bit confusing here I use a and
B both for this and for this so I will fix this here I would use this
as x and y instead of a you'll be on the temp side x and y then PX
is and where P a is Q a h2o but this is going to be x and y so then
this end B plays very different role from this so because we assumed
that Q exists and so it has a map and a contra map then obviously
P will have an X map which is called in the scholars Eli rains the
cats lair is called I map not sure what is a good name but let\textsf{'}s go
let me call it X map so this will be defined this follows from a definition
and the laws identity and composition laws oops there is a mistake
must be G 2 followed by G 1 because their composition for the contravariant
art is the opposite order okay I'll fix that in the slide so this
is G 2 and G 1 the important idea is that once you have this cue it
means you already have map in B and country map in a and the ones
for those called separately and so it can be derived but these laws
hold because they're just positions of those functions and so therefore
these laws can be seen as consequence of this definition and it\textsf{'}s
not a new a new assumption or new requirement it\textsf{'}s a consequence of
the definition and so that\textsf{'}s why we believe it\textsf{'}s reasonable to impose
these laws so as I said all exponential polynomial type constructors
are pro founders because in all of them there will be type expressions
of this kind the type parameter must be either on the right or on
the left and so then you can easily relate the covariant and contravariant
by different type parameters and then we can define the Q that you
are required to have and then you have your pro functor defined and
you prove that easily just applicative proof functor is defined in
exactly the same way using zip and wrapped unit with the same boss
there is no corresponding app method but there is a pure method from
a to P because you can take wrapped unit which is p1 and you can X
map it with a function from a to one and the function from 1 to a
which you will always have since you have an a then you have a function
from 1 to a and the function from a to 1 you always have and so you
can X map your rapped unit from P 1 to P a given a so that\textsf{'}s the pyramid
but you cannot derive app or any analog event I believe so what are
the constructions all the previous constructions still work because
profounder is a superset of both a functor and contra factor is any
factor is a profounder any control hunter is a pro factor is a superset
of both of them so all of the constructions we had before also cold
as proof under constructions in the trivial sense however there are
more construction so the product construction again then there is
the monoid addition then there is the free pointed and a function
now a function works and all these constructions work in exactly the
same way as they work for the factor and this works in exactly the
same way as it works for contra factor you see here it\textsf{'}s a functor
here it\textsf{'}s not it\textsf{'}s not control factor it\textsf{'}s a factor it\textsf{'}s important
it doesn't work doesn't seem to work for control factors really confer
pro factors I tried but I couldn't make this construction work I could
implement the types of zip and the wrapped Union but I could not get
associativity law to hold for for this kind of construction so I don't
think this construction works but these constructions certainly work
in the composition also in order to find that they work you don't
need any more proofs actually you just look at your old proofs and
you find that you aren't using the property of G as functor or contra
factor or anything you don't use map on G when you do these things
you don't use contra map either in this construction we use pure but
you have pure for the pro functor in this construction we use only
zip and wrapped in it and nothing else with this construction you
only use zip and wrapped unit in this construction you only use a
functor for F but you don't use anything for Q except wrapped in it
and zip and similarly here and so all these constructions actually
go through with no further proofs necessary I was able to find out
that these constructions work by pretty much try on air I hope I found
all the important constructions and that exists improves so for example
here we don't use we use map on H but we don't use anything on G we
only do mark on each not never on G so I'm pretty sure that this construction
does not work and I'm pretty sure these constructions all work because
these proofs do not use properties of pro factor other than zip and
wrapped unit let me just check the sum of a and govt so this this
is construction that uses pure so let me just look at the proof of
that construction here this it does not use the functor instance on
G just uses the zip and rap unit there\textsf{'}s never any map there\textsf{'}s a pure
so we need a pure on G that\textsf{'}s true and it needs to satisfy identity
law that\textsf{'}s true other than that we do not use map on anywhere so we
we use the equivalences yes but those are available for pro factors
in the same way they are available for country factors we can for
example use x map and rearrange tuples in the forward direction in
the backward direction and then this will give us a rearrangement
of tuples in the type of the pro factor so yeah so to summarize these
are the constructions i believe exist for applicative functors contra
hunters and cro factors now i'd like to have a little comment on an
interesting property of applicative factors which is symmetry or commutativity
but before symmetry because it\textsf{'}s not really committed to beauty literally
speaking monoidal operation can be commutative or symmetric with respect
to the Pregnant\textsf{'}s it\textsf{'}s probably better to say cumulative it\textsf{'}s just
this property now if you want to apply the same property to zip so
you I would use this notation for the zip operation you cannot literally
say it FA of being must be equal to if BFA because there are different
types so you need to map the types by rearranging the types because
this is going to be of type F of a B and this is going to be of type
F of B a but if you implicitly say that this isomorphism is included
in the equivalence and you could write it like this so that is the
same symmetry property not not all applicative factors are symmetric
what does it mean that it is symmetric well it means that the effects
somehow are independent in such a way that the second effect is independent
of the first now in the implicative factor the second effect is independent
of the value returned by the first container of the value it is an
independent but it may not be independent of the effect and if it
is so then this symmetry will not hold but there are some examples
where it holds for example list is symmetric manifestly so because
you can just permit the list dominance a good example of non symmetric
applicative frontier is parsers we have looked at this briefly parsers
are not symmetric because when you do applicative composition of parsers
the first parser already might have consumed some part of the input
string and the second parser starts from the place left over by the
first parser well the first parser stopped and so the second parser
depends on this effect now the value returned by the first parser
does not indicate necessarily a position where it stopped the value
is the value it parsed out of the input and the second part is independent
of that value but it depends implicitly on where the first parser
stopped and so the parser combination using applicative composition
would not satisfy this requirement of symmetry also if you define
anything through the mu net most likely it\textsf{'}s not going to be symmetric
well for lists we know it is not symmetric we have seen that the order
is different in the result when you define zip through through the
moment but we know that for lists the mu not defined zip is not usually
what you want you want applicative defined zip which is incompatible
for lists all polynomial factors with monoidal coefficients that are
symmetric will be symmetric applicative entries because we have seen
how polynomial factors combine their values and then so the minute
they put commute these elements in a different order if you change
the order of these two so the moon at zip is not symmetric now the
polynomial one is symmetric because it basically combines elements
like this so if you put this first it doesn't matter it will still
take these two and combine with these two so similarly here so the
typical polynomial factor with symmetrical B with symmetric when one
of the coefficients like integer which is a symmetrical mono at boolean
of symmetrical node with strings and string concatenation is not as
commutative monoid so that would not be commutative and so the polynomial
factor with strength coefficients would not be a symmetric or neither
or commutative may be gathered aside but I've seen usage of the word
symmetric so I would say the commutative or symmetric negative funky
will be probably the same meaning now it\textsf{'}s interesting to say that
first of all most of our constructions preserve symmetry so if if
you think about how we defined all these constructions of the last
portion there was deep in this functor and it was symmetric in how
you provided arguments for this zip so if G is symmetric then this
is also symmetric and G is symmetric this is symmetric if G and H
are symmetrical commutative then this is also commutative and so on
so there are some constructions that would not be symmetric usually
coming from units but all these constructions are symmetric so if
you have symmetric coefficients and if you have symmetric applicative
factors and you combine them using any of these constructions that
we have seen and you get again symmetric wickety factors and control
factors and pro functions work exactly the same way and they have
the same commutativity property because well we have formulated the
cumulative 'ti with symmetry property using this which is a map but
if this were a contra factor that we would just use contra map here
and this function is an isomorphism so it is available in both directions
and so we can use X map as well because we have this in both directions
commutativity or symmetry makes it easier to prove associativity for
negative factors I have not used this in my proofs but mostly because
I have specific instructions I didn't want to assume symmetry but
if you had a commutative applicati factor that you could just rearrange
this into this by permuting and and permitting this with this so you
have that which is almost what you need to prove associative you just
need to swap FC and FA and so that\textsf{'}s perhaps much less work to do
that we just compute this and then you swap FA and I've seen it and
you demand that the result be the same up to a swapping of types and
that\textsf{'}s less work for symmetry for symmetric code then another wise
that\textsf{'}s otherwise you'd have to first compute this separately then
you compute this separately but in most cases it\textsf{'}s significantly easier
to prove I think it was proved that we can see so I would like to
finish this tutorial with an overview of standard filter classes using
category theory so strictly speaking this is just kind of a theoretical
perspective which doesn't add much practically to programming it\textsf{'}s
more or less just a justification as a an explanation of why these
factors exist why these specific properties exist and why we have
assurance that we have the right laws for them and here\textsf{'}s how it goes
so consider typeclasses such as functor filterable monad applicative
contra functor and so on each of these when we consider them depth
the laws for them we found a function with type signature that looked
like a lifting and by lifting I mean it was a function of higher order
that a function like this and produced another function and the function
on the left was of one type and the function on the right was of a
different type and on the right it was in the function f so always
this lifting took something and produced a function from FA to FB
so it took this produced a fatal FB took this was his flat map produced
a fatal be missus app it took this produced a fatal of me contra factor
took this produced a fatal FB this should be X map rather than Dyna
prevented own I will fix this in the slides it took something it gives
a fate of B and so on so this is what I mean by lifting it is this
kind of functions type signature that takes some kind of function
as argument and returns this kind of function FA to FB let\textsf{'}s look
carefully at the types of functions that are taken as arguments by
these liftings all of these our functions of a types contain a and
B their functions from something to something that contains a and
B in some way this is what we consider to be a category in the previous
lecture namely it\textsf{'}s a description of what is the type of a function
that we twist so we kind of twist a function type we don't just take
a to be like here we twist it a bit we add something on top of it
to be like or we can even reverse the area we don't have B to a instead
of A to B or we have a to F of B or we have a to one plus B or B to
1 plus a or somewhere so it\textsf{'}s kind of twisted it\textsf{'}s a twisted function
type and so all these liftings take a twisted function type and give
me a function type in the functor so functor transformation second
thing we notice is that when we looked at the laws that need to be
acquired for these typeclasses each of these strange twisted function
types had identity and composition laws there was always a way to
compose two of these and get another one of those so for example we
composed a to B and B to C and we got a to C we can post a to one
plus B beta 1 plus C and we got a to 1 plus C we can pose a to FB
b to FC we get a 2 FC we can pose F of A to B and F of B to C we get
F of A to C and so we compose functions of this type also we had an
identity function of this twisted type here it was the ordinary identity
this was a pure option that creates so 8 goes to 0 plus a so it creates
a sum away this was the pure function of the mullet this was the pure
of identity this is identity we did not consider those things in this
way but they have exactly the same structure there is an identity
function of this twisted type and there is a composition for functions
of twisted type so in our simplified definition of category that\textsf{'}s
what category is is a twisted type for functions such that we can
compose these twisted functions and we have a twisted identity so
here in applicative i noted it like this this is the twisted identity
and this is a twisted composition and so for example a function of
a value of type f a to b can be composed with other values of type
say F B to C and you get a value of type F a to B and F a to sir sorry
so that\textsf{'}s the general scheme of things it seems for each of these
examples we have this twisted function type a twisted composition
of these twisted function types and the twisted identity and the laws
of identity and composition hold in other words composition of identity
and something is equal to that something and composition is associative
these are the axioms of a category the category laws so to speak a
category is described by saying what is the type of the twisted function
that it has a twisted function is also called morphism so what is
the type of morphism that the category has this type should somehow
depend on a and B so there must be a and B in this type somewhere
other than that we don't know what that type is it could be many different
type expressions having a and B in it and it better be some kind of
function it could be like this as well it\textsf{'}s not clear exactly what
qualifies is fun is this a function we don't know one example of applicative
is a monoid with no dependence of type parameter that\textsf{'}s what the functions
prickly speaking but it doesn't matter a morphism is just a type such
that you have an identity element of this type and the composition
of elements of this type and the type is indexed by two type parameters
a and B what\textsf{'}s all it needs to be it\textsf{'}s just the morphism is a type
expression depending on two parameters and that\textsf{'}s it each category
has its own different definition of what that morphism is some categories
have names this category is the plain type category which is not twist
it\textsf{'}s just a function it was not Christian so this is the category
of ordinary functions this is a class Li category of the function
f this is the class the category of the font option so it\textsf{'}s a specific
example actually of this with the option is a specific F this is the
applicative category but that\textsf{'}s just what I call it there is no accepted
name for it it seems this is the opposite category category that all
functions with opposite type signature I don't know what this is called
this is the opposite to option class Lee so the generalization that
category theory cell gives us here is that all of these typeclasses
are seen in one kind of way you define them by specifying the type
of the morphism defines the special some special category that you're
interested in automatically you demand laws the category laws is also
you specified identity morphisms once you have specified this and
demanded that laws of category and also natural T there must be in
all of these naturality laws which relate like we have here in here
the naturality laws which relate this twisted composition and the
ordinary usual F map so that must be their natural T because we are
now we need to always relate this category and the category or working
with so but once you specify these was which are always the same always
the same laws so they're not different somehow in each in each case
there are the same laws just for a different category it\textsf{'}s a very
powerful generalization where you basically say everything is fixed
except for the type of the morphism and you can choose that type in
many different ways and you get different typeclasses automatically
with all the period clause automatically chosen for you remember the
filterable functor had four laws which were kind of ad hoc if you
look at them like that moon had also had laws that we kind of guessed
applicative we kind of guessed what these laws must be but if you
look at those from the category point of view they're not at all arbitrary
once you specified this type expression for the morphism type or the
twisted function type everything is fixed all the laws are fixed you
give you derive all the possible constructions for the factors that
satisfy these laws all the laws for example for zip and wrapped unit
are equivalent as we have shown to the category laws for this category
and the same thing we have shown in previous chapters about filter
balls and moments the category laws are equivalent to the laws obtained
previously in terms of different functions so because the category
laws are always the same it\textsf{'}s just that the types are different we
have assurance that we found the right laws that all these classes
are somehow correctly defined we didn't forget some law for filterable
also we didn't have too many laws we have exactly the laws we want
and that\textsf{'}s one thing the second thing we we obtained from the systematic
picture is we can try to generalize and find more typeclasses I mean
we have found these typeclasses are there any more have we forgotten
some interesting typeclasses how do we generalize well in this scheme
the only way to generalize is to change the type of morphism in the
category and let\textsf{'}s see we had a to be we had a to F of B we had F
of a to b but we didn't have F of a going to B we didn't have that
why not indeed excellent question and if we consider that as the type
of the categories morphism and demand that these functions twisted
functions or morphisms have a composition law and identity one we
obtained something called the comonad we have not yet considered comonad
and we did not find any other motivation to consider it but this is
a this is a motivation that kind of falls out of this consideration
so we have a to be it says a to FB with some specific f we could take
some other specific F and see what happens then maybe it\textsf{'}s not something
interesting and I've generalized filterable so from option to something
else maybe it\textsf{'}s useful maybe not monad applicative now doesn't seem
to be any other way of putting F on here we already exhausted everything
we have a to be we have F a to F of B F of a to b f a to B now let\textsf{'}s
reverse we have B to a we have B to one plus a what about B to F of
a what about F of B to a and what about F B to a I tried some of them
and they don't work so actually this scheme does not always work so
you can't choose an arbitrary type expression here and expect it to
work in what in what says it do I say that it does not work in the
sense that you cannot find a composition law for this category that
would at the same time fit with this scheme so because what you want
is not just some arbitrary category with some arbitrary composition
law but you also want to lift it then to your functor and that\textsf{'}s the
that\textsf{'}s what doesn't work so you basically find that there aren't any
factors that satisfy this property so another thing that is not great
about it is that some typeclasses don't seem to be covered by this
scheme such as for example contra applicative and pro functor replicative
i haven't been able to find a formulation of them using this scheme
so maybe there is a trick that I'm missing but right now and especially
since for example contract leakages don't have an app they don't so
you cannot write like this you know you could think contra black Egyptians
contra functor means this category and applicative means this category
contra placated means f of B to e no so you can't have this kind of
thing with F of B to a so the conclusion is we have a very interesting
and general scheme that shows that there are some typeclasses like
these that are in some sense natural there\textsf{'}s some sense they are all
part of one approach which is define a category lifts from that category
morphism to this morphism for some functor f derive the laws from
the category laws we must have here liftings laws our function was
they're fixed as well I didn't talk about this but the laws for this
are fixed because it\textsf{'}s of just a functor from one category to another
and so the laws are identity must go to identity composition must
go to composition so again no freedom in choosing the laws we have
fixed laws they're fixed laws here we derive then what are the properties
of the function f such that these laws hold and we formalize this
as a typeclass so in this way we can make a case that all these classes
all these typeclasses are in some sense standard they are all obtained
from the same method and their laws are fixed so there we have good
assurance that we we have found the right louis and the right typeclasses
and we can generalize so communal is one example that follows from
this with this choice of the morphism type some possibilities like
contra monad you know when you try to do moon ad and do B to F FA
for example it doesn't seem to work and some classes like contra functors
applicatives don't seem to be covered by risk but other than this
seems to be a very powerful generalization and an elegant way of conceptualizing
and justifying that the laws are correct and understanding why the
laws must be like that and how to analyze those factors and so for
each of these types we have thoroughly analyzed what factors have
the properties that they have that they must have and in the later
tutorial we might do the same for como nuts so this is what category
theory brings it\textsf{'}s kind of an conceptual generalization it is not
so much in terms of specific code that we couldn't write until we
saw this table but in a certain sense it shows a direction in which
we could go on and that\textsf{'}s so far what I found category theory gives
so to finish off this tutorial here are some exercises for you along
the lines of what we have been doing and some of these exercises require
proof and others don't indicate where so here you do need to prove
and here you don't here you don't and here you do good luck so this
concludes the tutorial in Chapter eight 
\end{comment}

